View source for RANDU


[[Image:Randu.png|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 [[2D geometric model|two-dimensional]] [[Plane (mathematics)|plane]]s.]]

'''RANDU'''<ref name=":0">Compaq Fortran   Language Reference Manual (Order Number: AA-Q66SD-TK) September 1999   (formerly DIGITAL Fortran and DEC Fortran 90)</ref>{{Use dmy dates|date=July 2012}} is a [[linear congruential generator|linear congruential]] [[pseudorandom number generator]] (LCG) of the [[Park–Miller random number generator|Park–Miller type]], which has been used since the 1960s.<ref name="Entacher-2000">
{{cite web
 | last = Entacher
 | first =  Karl
 | title = A collection of classical pseudorandom number generators with linear structures - advanced version
 | date = June 2000
 | work =
 | url=http://random.mat.sbg.ac.at/results/karl/server/server.html
 | accessdate = 8 August 2013
}}</ref>  It is defined by the [[Recursion|recurrence]]:

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

with the initial seed number, <math>\scriptstyle V_0</math> as an [[even and odd numbers|odd number]]. It generates pseudorandom [[integer number|integers]] <math>\scriptstyle V_j</math> which are [[uniform distribution (discrete)|uniformly distributed]] in the interval {{nowrap|[1, 2<sup>31</sup> − 1]}}, but in practical applications are often mapped into pseudorandom [[rational number|rationals]] <math>\scriptstyle X_j</math> in the interval {{nowrap|(0, 1)}}, 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,<ref>[[Donald Knuth|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.]</ref> and was described as "truly horrible" by [[Donald Knuth]].<ref>Knuth (1998), p. 188</ref> 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 2<sup>31</sup> and <math>65539</math> <math>(\text{i.e., }2^{16} + 3)</math> calculations could be done quickly, using special features of some computer hardware.

== Problems with multiplier and modulus ==
In general, when an LCG with modulus 2<sup>31</sup> is used to produce points (x<sub>k</sub>, x<sub>k+1</sub>, x<sub>k+2</sub>) in 3-dimensional space, the points fall into no more than 2,344 parallel planes<ref>{{cite journal|author=Marsaglia, George|year=1968|title=Random Numbers Fall Mainly in the Planes|url=http://www.pnas.org/content/61/1/25.citation|journal=Proc. Natl. Acad. Sci. U.S.A.|volume=61|issue=1|pages=25–28|doi=10.1073/pnas.61.1.25|pmc=285899}}</ref>, a result which indicates an LCG is unsuitable for [[Monte carlo Simulation|Monte Carlo simulation]]. Choice of multiplier determines the number of planes. To show the problem with 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 becomes, after expanding the quadratic factor:

:<math>x_{k+2}=(2^{32}+6 \cdot2^{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>

As a result of this correlation, each point lies in one of a set of parallel planes 2<sup>31</sup> apart, 15 of which intersect the 2<sup>31</sup> x 2<sup>31</sup> x 2<sup>31</sup> cube containing the points. 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>ref. 7 of http://portal.acm.org/citation.cfm?id=363827</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>[http://tex.loria.fr/litte/knuth-interview Interview with Donald Knuth]</ref> but there were still FORTRAN compilers using it as late as 1999.<ref name=":0" />

==Sample output==

The start of the RANDU's output period for the initial seed <math>\scriptstyle V_0 = 1</math> is:
: 1, 65539, 393225, 1769499, 7077969, 26542323, … {{OEIS|A096555}}

==References==
{{Reflist|30em}}

== External links==
{{Wikiquote}}

[[Category:Pseudorandom number generators]]