Knuth on random number generators

[Greg Lee]

On January 8, Professor Donald Knuth gave an informal lecture at
Stanford University on the current state of random number
generation. David Hough suggested that I post  a summary of some of
the more interesting points.  As always, I am responsible for any 
errors; details and definitive word will have to come from Professor 
Knuth.

Professor Knuth first described the historical background for the
study of RNG and, in particular, the state of computing when he
wrote volume II of "The Art of Computer Programming."  At that time
his world was mostly 36-bit machines and the move to 32-bits was
viewed as a step down in capability.  Other changes between then and
now include vastly increased memory capacity, cheap MIPS, and demand for
many  random numbers.

Next he discussed multiplicative congruential generators.  For
undemanding applications on 32-bit architectures, he seems to be
satisfied with xnew =  48271*xold mod 2**31-1.  This can be
implemented portably in a few lines of C or FORTRAN.

For longer period generators, the story is more complicated.  The
state of the art seems to be "lagged Fibonacci generators." These are
based on recursions x[n] = x[n-K] + x[n-L], where K and L are
constants.   Knuth has been using the particular generator based on
K=24 and L=55 in his own work. (This is described in his book "The
Stanford GraphBase"). 

Generators of this type pass most tests of randomness and are good
enough for most applications.  However,  they fail some recently
discovered tests.  The birthday test (Marsaglia) looks at spacings
between pairs of random numbers.  The second test looks at 0-1
random walks.  Both of these failure modes have been analyzed  and
represent genuine flaws in the lagged Fibonacci method.

Knuth's current recommendation runs roughly as follows: use a lagged
Fibonacci generator but keep only the first N of every M numbers
generated.  The sequence resulting from the batches of N passes all
known tests, including the two that fail on the basic generator.  A
typical value for  (N,M) might be 100 and 1,000. 

Finally, on an unrelated note, Knuth is working full time on volume 4 
of "The Art...".
_______________________________________________
Greg Lee
811 Guinda Street, Palo Alto CA 94301
(415) 326-6468 (voice) / (415) 328-9259 (fax)
gregleeaacm.org