RANDU

thumb|right|[[Three-dimensional space|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 an obsolete method for generating random numbers used primarily in the 1960s and 1970s. defined by the recurrence

: <math>V_{j+1} = 65539 \cdot V_j \bmod 2^{31}</math>

with the initial seed number <math>V_0</math> as an odd number. It generates pseudorandom integers <math>V_j</math> which are uniformly distributed in the interval , but in practical applications are often mapped into pseudorandom rationals <math>X_j</math> in the interval , by the formula

: <math>X_j = \frac{V_j}{2^{31.</math>

IBM's RANDU is widely considered to be one of the most ill-conceived random number generators ever designed, and was described as "truly horrible" by Donald Knuth. It fails the spectral test badly for dimensions greater than 2, as shown below.

The reason for choosing these particular values for the multiplier and modulus had been that with a 32-bit-integer word size, the arithmetic of mod 2³¹ and <math>65539 = 2^{16} + 3</math> calculations could be done quickly, using bitwise operators in hardware, but the values were chosen for computational convenience, not statistical quality.

Problems with multiplier and modulus

For any linear congruential generator with modulus m used to generate points in n-dimensional space, the points fall in no more than <math>(n! \times m)^{1/n}</math> parallel hyperplanes. This indicates that low-modulus LCGs are unsuited to high-dimensional Monte Carlo simulation. For m = 2³¹ and n = 3, an LCG could have up to 2344 planes, theoretical maximum. A much tighter upper bound is proved in the same Marsaglia paper to be the sum of the absolute values of all the coefficients of the hyperplanes in standard form. That is, if the hyperplanes are of the form Ax₁ + Bx₂ + Cx₃ = some integer such as 0, 1, 2 etc, then the maximum number of planes is |A| + |B| + |C|. This misbehavior was already detected in 1963 on a 36-bit computer, and carefully reimplemented on the 32-bit IBM System/360. It was believed to have been widely purged by the early 1990s but there were still FORTRAN compilers using it as late as 1999.