Misplaced Pages

RANDU

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
Pseudorandom number generator

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 (LCG) of the Park–Miller type, which was used primarily in the 1960s and 1970s. It is 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 , 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 2 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 = 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 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 2 chosen for RANDU. Consider the following calculation where every term should be taken mod 2. 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}=x_{k}}

(because 2 mod 2 = 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}.}

Summing the absolute values of the coefficients, we get no more than 16 planes in 3D, becoming only 15 planes on closer examination, as shown in the diagram above. Even by the standards of LCGs, this shows that RANDU is terrible: using RANDU for sampling a unit cube will only sample 15 parallel planes, not even close to the upper limit of ⌊ ( 2 31 × 3 ! ) 1 / 3 ⌋ = 2344 {\displaystyle {\Big \lfloor }{\big (}2^{31}\times 3!{\big )}^{1/3}{\Big \rfloor }=2344} planes.

As a result of the wide use of RANDU in the early 1970s, many results from that time are seen as suspicious. 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.

Sample output

The start of the RANDU's output period for the initial seed V 0 = 1 {\displaystyle V_{0}=1} is

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

References

  1. ^ Compaq Fortran Language Reference Manual (Order Number: AA-Q66SD-TK) September 1999 (formerly DIGITAL Fortran and DEC Fortran 90).
  2. Entacher, Karl (June 2000). "A collection of classical pseudorandom number generators with linear structures – advanced version". Archived from the original on 18 November 2018.
  3. Knuth D. E. The Art of Computer Programming, Volume 2: Seminumerical Algorithms, 2nd edition. Addison-Wesley, 1981. ISBN 0-201-03822-6. Section 3.3.4, p. 104: "its very name RANDU is enough to bring dismay into the eyes and stomachs of many computer scientists!"
  4. Knuth (1998), p. 188.
  5. ^ Marsaglia, George (1968). "Random Numbers Fall Mainly in the Planes". Proc. Natl. Acad. Sci. U.S.A. 61 (1): 25–28. Bibcode:1968PNAS...61...25M. doi:10.1073/pnas.61.1.25. PMC 285899. PMID 16591687.
  6. Press, William H.; et al. (1992). Numerical Recipes in Fortran 77: The Art of Scientific Computing (2nd ed.). ISBN 0-521-43064-X.
  7. Greenberger, Martin (1 March 1965). "Method in randomness". Commun. ACM. 8 (3): 177–179. doi:10.1145/363791.363827. ISSN 0001-0782.
  8. "Donald Knuth – Computer Literacy Bookshops Interview". 7 December 1993. Archived from the original on 28 March 2022.

External links

  • Quotations related to RANDU at Wikiquote
Category: