Editing RANDU (section)

== 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.<ref name=marsaglia>{{cite journal |author=Marsaglia, George |year=1968 |title=Random Numbers Fall Mainly in the Planes |journal=Proc. Natl. Acad. Sci. U.S.A. |volume=61 |issue=1 |pages=25–28 |doi=10.1073/pnas.61.1.25 |pmc=285899 |pmid=16591687 |bibcode=1968PNAS...61...25M |doi-access=free}}</ref> This indicates that low-modulus LCGs are unsuited to high-dimensional [[Monte Carlo simulation]]. For ''m'' = 2<sup>31</sup> 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''<sub>1</sub> + ''Bx''<sub>2</sub> + ''Cx''<sub>3</sub> = some integer such as 0, 1, 2 etc, then the maximum number of planes is |''A''| + |''B''| + |''C''|.<ref name=marsaglia/>

Now we examine the values of multiplier 65539 and modulus 2<sup>31</sup> chosen for RANDU. Consider the following calculation where every term should be taken mod 2<sup>31</sup>. Start by writing the recursive relation as

: <math>x_{k+2} = (2^{16} + 3) x_{k+1} = (2^{16} + 3)^2 x_k,</math>

which after expanding the quadratic factor becomes

: <math>x_{k+2} = (2^{32} + 6 \cdot 2^{16} + 9) x_k =[6 \cdot (2^{16} + 3) - 9] x_{k}</math>

(because {{nowrap|2<sup>32</sup> mod 2<sup>31</sup> {{=}} 0}})
and allows us to show the correlation between three points as

: <math>x_{k+2} = 6x_{k+1} - 9x_{k}.</math>

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 <math>\Big\lfloor\big(2^{31} \times 3!\big)^{1/3}\Big\rfloor = 2344</math> planes.

As a result of the wide use of RANDU in the early 1970s, many results from that time are seen as suspicious.<ref name="press92">{{cite book |author=Press, William H. |year=1992 |title=Numerical Recipes in Fortran 77: The Art of Scientific Computing |edition=2nd |isbn=0-521-43064-X |display-authors=etal}}</ref> This misbehavior was already detected in 1963<ref>{{Cite journal |last=Greenberger |first=Martin |date=1965-03-01 |title=Method in randomness |url=https://doi.org/10.1145/363791.363827 |journal=Commun. ACM |volume=8 |issue=3 |pages=177–179 |doi=10.1145/363791.363827 |issn=0001-0782}}</ref> on a 36-bit computer, and carefully reimplemented{{clarify|date=June 2016}} on the 32-bit [[IBM System/360]]. It was believed to have been widely purged by the early 1990s<ref>{{cite web |url=http://tex.loria.fr/litte/knuth-interview |title=Donald Knuth – Computer Literacy Bookshops Interview |date=1993-12-07 |archive-url=https://web.archive.org/web/20220328201420/http://tex.loria.fr/litte/knuth-interview |archive-date=2022-03-28 |url-status=dead}}</ref> but there were still FORTRAN compilers using it as late as 1999.<ref name=":0" />