RANDU

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 $2^\{31\}$ 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 $2^\{31\}$, 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 $2^\{31\}$) 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.Fact|date=November 2007

ample output

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

1 65539 393225 1769499 7077969 26542323 95552217 334432395 1146624417 1722371299 14608041 ... 134633675 1893599841 1559961379 907304297 2141591611 388843697 238606867 79531577 477211307 1

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).

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.