[R] efficient R code

[Thomas Lumley]

On Wed, 9 Feb 2005, Knut M. Wittkowski wrote:

> Last Friday, Gregory Chaitin (http://www.umcs.maine.edu/~chaitin/lm.html) 
> mentioned that there can be no proof that a given code is the shortest for a 
> problem, even within a language.

I presume he said something more like `for some problems there is no 
proof' or `there is no procedure for constructing a proof'

You can prove that function(x) x+1 is the shortest function for computing 
x+1 in R by listing all the shorter functions and verifying that none of 
them computes x+1, both of which tasks can be done fairly fast.  This 
approach doesn't generalise because you can't give a general way to 
perform the second step: checking that none of the smaller programs works.

I would expect that the TDT falls in the category of problems checkable by 
enumeration.


>				Still, the script below, a replacement of 
> the "TDT", one of the most frequently used tests in genetics 
> (http://mustat.rockefeller.edu under "downloads") may get close. It contains 
> a few additional bytes for clarity, as in (2^1) for 2, but, otherwise, I 
> don't think one could make this much shorter, especially the part that does 
> the exact distribution.
>
> I'm looking forward to comments on improving the programming efficiency for 
> this problem. (The "return(...)" seems to be necessary in R only.)
>

The return() should not be necessary in R.

 	-thomas

Thomas Lumley			Assoc. Professor, Biostatistics
tlumley at u.washington.edu	University of Washington, Seattle