RANDU is an obsolete method for generating random numbers used primarily in the 1960s and 1970s. It is a linear congruential generator (LCG) of the Park–Miller type defined by the recurrence
V j + 1 = 65539 ⋅ V j mod 2 31 {\displaystyle V_{j+1}=65539\cdot V_{j}{\bmod {2}}^{31}}
with the initial seed number V 0 {\displaystyle V_{0}} as an odd number. It generates pseudorandom integers V j {\displaystyle V_{j}} which are uniformly distributed in the interval [0, 231 − 1], but in practical applications are often mapped into pseudorandom rationals X j {\displaystyle X_{j}} in the interval (0, 1), by the formula
X j = V j 2 31 . {\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, 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 231 and 65539 = 2 16 + 3 {\displaystyle 65539=2^{16}+3} 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 ( n ! × m ) 1 / n {\displaystyle (n!\times m)^{1/n}} parallel hyperplanes. This indicates that low-modulus LCGs are unsuited to high-dimensional Monte Carlo simulation. For m = 231 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 Ax1 + Bx2 + Cx3 = some integer such as 0, 1, 2 etc, then the maximum number of planes is |A| + |B| + |C|. Now we examine the values of multiplier 65539 and modulus 231 chosen for RANDU. Consider the following calculation where every term should be taken mod 231. Start by writing the recursive relation as
x k + 2 = ( 2 16 + 3 ) x k + 1 = ( 2 16 + 3 ) 2 x k , {\displaystyle x_{k+2}=(2^{16}+3)x_{k+1}=(2^{16}+3)^{2}x_{k},}
which after expanding the quadratic factor becomes
x k + 2 = ( 2 32 + 6 ⋅ 2 16 + 9 ) x k = [ 6 ⋅ ( 2 16 + 3 ) − 9 ] x k {\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
x k + 2 = 6 x k + 1 − 9 x k . {\displaystyle x_{k+2}=6x_{k+1}-9x_{k}.}
… excerpt ends here. Continue reading the full article.
