RANDU

From Wikipedia, the free encyclopedia

You have new messages (last change).
Plot of 3000 points generated with RANDU. It is clearly seen that the points fall in 15 planes
Plot of 3000 points generated with RANDU. It is clearly seen that the points fall in 15 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 V0 odd.

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 = 216 + 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:

xk + 2 = (216 + 3)xk + 1 = (216 + 3)2xk

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:

xk + 2 = 6xk + 1 − 9xk

As a result of this correlation the points in three dimensional space fall in a comparatively small number of planes, 15 to be exact. As a result of the wide use of RANDU in the early 70's many results from that time are seen as suspicious.

...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: Seminumerical Algorithms, 3rd edition (Addison-Wesley, Boston, 1998).
  • Press, William H., et al. (1992). Numerical Recipes in Fortran 77: The Art of Scientific Computing, 2nd edition. ISBN 0-521-43064-X.
Retrieved from "http://en.wikipedia.org../../../r/a/n/RANDU_209a.html"
In other languages