RANDU

From Wikipedia, the free encyclopedia

Three-dimensional plot of 100,000 points generated with RANDU. It is clearly seen that the points fall in 15 two-dimensional planes.

RANDU is an infamous linear congruential pseudorandom number generator which has been used since the 1960s. It is defined by the recurrence:

$V_{j+1} \equiv (65539 V_j) \mod 2^{31}\,$

with $V 0$ odd.

Pseudo-random numbers are calculated as:

$X_{j} \equiv V_{j} / 2^{31}\,$

It is widely considered to be one of the most ill-conceived random number generators designed. Notably, it fails the spectral test badly for dimensions greater than 2.

The reason for choosing these particular values is that with a 32 bit integer word size the arithmetic of mod $231$ and $65539 = 2 16 + 3$ calculations could be done quickly. To show the problem with these values consider the following calculation where every term should be taken mod $231$ , we start by writing the recursive relation as:

$x_{k+2}=(2^{16}+3) x_{k+1}=(2^{16}+3 )^2 x_{k}\,$

which becomes, after expanding the quadratic factor:

$x_{k+2}=(2^{32}+6 \cdot2^{16} +9 )x_{k}=[6 \cdot (2^{16}+3)-9]x_{k}\,$

and allows us to show the enormous correlation between three points as:

$x_{k+2}=6x_{k+1}-9x_{k}\,$

As a result of this correlation the points in three dimensional space (mod $231$ ) fall in a comparatively small number of planes, 15 to be exact (see Marsaglia's paper). As a result of the wide use of RANDU in the early 70's many results from that time are seen as suspicious.^{[citation needed]}

[edit] Sample output

The start and end of RANDU’s output (when started with a seed of 1):

[edit] Quotes

...its very name RANDU is enough to bring dismay into the eyes and stomachs of many computer scientists! —Donald Knuth

One of us recalls producing a “random” plot with only 11 planes, and being told by his computer center’s programming consultant that he had misused the random number generator: “We guarantee that each number is random individually, but we don’t guarantee that more than one of them is random.” Figure that out. —Press, William H., et al. (1992).

[edit] References

Donald E. Knuth, The Art of Computer Programming, Volume 2, 3rd edition (Addison-Wesley, Boston, 1998).
Marsaglia, George (1968), "Random Numbers Fall Mainly in the Planes," Proc National Academy of Sciences 61, 25-28.
Press, William H., et al. (1992). Numerical Recipes in Fortran 77: The Art of Scientific Computing, 2nd edition. ISBN 0-521-43064-X.