# RANDU

Three-dimensional plot of 100,000 values generated with RANDU. Each point represents 3 consecutive pseudorandom values. It is clearly seen that the points fall in 15 two-dimensional planes.

RANDU is a linear congruential pseudorandom number generator of the Park–Miller type, which has been used since the 1960s.[1] It is defined by the recurrence:

${\displaystyle V_{j+1}=65539\cdot V_{j}\,{\bmod {\,}}2^{31}\,}$

with the initial seed number, ${\displaystyle \scriptstyle V_{0}}$ as an odd number. It generates pseudorandom integers ${\displaystyle \scriptstyle V_{j}}$ which are uniformly distributed in the interval [1, 231 − 1], but in practical applications are often mapped into pseudorandom rationals ${\displaystyle \scriptstyle X_{j}}$ in the interval (0, 1), by the formula:

${\displaystyle X_{j}={\frac {V_{j}}{2^{31}}}}$.

IBM's RANDU is widely considered to be one of the most ill-conceived random number generators ever designed.[2] It fails the spectral test badly for dimensions greater than 2, and every integer result is odd. However, at least eight low-order bits are dropped when converted to single-precision (32 bit, 24 bit mantissa) floating-point.

The reason for choosing these particular values is that with a 32-bit-integer word size, the arithmetic of mod 231 and ${\displaystyle 65539}$ ${\displaystyle ({\text{i.e., }}2^{16}+3)}$ calculations could be done quickly, using special features of some computer hardware.

## Problems with multiplier and modulus

To show the problem with these values, of multiplier 65539 and modulus 231, consider the following calculation where every term should be taken mod 231. Start by writing the recursive relation as:

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

which becomes, after expanding the quadratic factor:

${\displaystyle x_{k+2}=(2^{32}+6\cdot 2^{16}+9)x_{k}=[6\cdot (2^{16}+3)-9]x_{k}\,}$
because 232 mod 231 = 0

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

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

As a result of this correlation, the points in three-dimensional space (mod 231) fall in 15 planes.[3][not in citation given] As a result of the wide use of RANDU in the early 1970s, many results from that time are seen as suspicious.[4]

This misbehavior was already detected in 1963[5] on a 36-bit computer, and carefully reimplemented[clarification needed] on the 32-bit IBM System/360.

## Sample output

The start and end of the RANDU’s output period for the initial seed ${\displaystyle \scriptstyle V_{0}=1}$ is:

1, 65539, 393225, 1769499, 7077969, 26542323, … (sequence A096555 in the OEIS)

## References

1. ^ Entacher, Karl (June 2000). "A collection of classical pseudorandom number generators with linear structures - advanced version". Retrieved 8 August 2013.
2. ^ Knuth D.E. The Art of Computer Programming, Volume 2: Seminumerical Algorithms, Second Edition. Addison-Wesley, 1981. ISBN 0-201-03822-6. Section 3.3.4, p. 104. [Extensive coverage of statistical tests for non-randomness.]
3. ^ Marsaglia, George (1968). "Random Numbers Fall Mainly in the Planes". Proc. Natl. Acad. Sci. U.S.A. 61 (1): 25–28. doi:10.1073/pnas.61.1.25.
4. ^ Press, William H.; et al. (1992). Numerical Recipes in Fortran 77: The Art of Scientific Computing (2nd ed.). ISBN 0-521-43064-X.
5. ^