RANDU: Difference between revisions
No edit summary |
template returned "{{{1}}}" for me > appeares 2b broken |
||
Line 18: | Line 18: | ||
It is widely considered to be one of the most ill-conceived random number generators designed. Notably, it fails the [[spectral test]] badly for dimensions greater than 2, and every result is odd. |
It is widely considered to be one of the most ill-conceived random number generators designed. Notably, it fails the [[spectral test]] badly for dimensions greater than 2, and every result is odd. |
||
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 |
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 = 2^{16} + 3</math> calculations could be done quickly. To show the problem with these values consider the following calculation where every term should be taken mod 2<sup>31</sup>, we start by writing the recursive relation as: |
||
:<math>x_{k+2}=(2^{16}+3) x_{k+1}=(2^{16}+3 )^2 x_{k}\,</math> |
:<math>x_{k+2}=(2^{16}+3) x_{k+1}=(2^{16}+3 )^2 x_{k}\,</math> |
Revision as of 18:16, 5 June 2012
![](http://upload.wikimedia.org/wikipedia/commons/thumb/3/38/Randu.png/220px-Randu.png)
RANDU is a linear congruential pseudorandom number generator of the Park–Miller type, which has been used since the 1960s.[1] It is defined by the recurrence:
with odd. It generates pseudorandom integers in the interval [1, 231 − 1] that in practical applications are often mapped into pseudorandom rationals in the interval (0, 1) by the formula:
- .
It is widely considered to be one of the most ill-conceived random number generators designed. Notably, it fails the spectral test badly for dimensions greater than 2, and every result is odd.
The reason for choosing these particular values is that with a 32 bit integer word size the arithmetic of mod 231 and calculations could be done quickly. To show the problem with these values consider the following calculation where every term should be taken mod 231, we start by writing the recursive relation as:
which becomes, after expanding the quadratic factor:
- because 232 mod 231 = 0
and allows us to show the enormous correlation between three points as:
As a result of this correlation, the points in three dimensional space (mod 231) fall in a comparatively small number of planes, 15 to be exact.[2] As a result of the wide use of RANDU in the early 1970s, many results from that time are seen as suspicious.[3]
This misbehavior was already detected in 1963[4] on a 36-bit computer, and carefully reimplemented on the 32-bit IBM360.
Sample output
The start and end of the RANDU’s output period for the initial seed is:
- 1, 65539, 393225, 1769499, 7077969, 26542323, …, 2141591611, 388843697, 238606867, 79531577, 477211307, 1 (sequence A096555 in the OEIS)
Quotations
…its very name RANDU is enough to bring dismay into the eyes and stomachs of many computer scientists!
One of us recalls producing a "random" plot with only 11 planes, and being told by his computer center's programming consultant that he had misused the random number generator: "We guarantee that each number is random individually, but we don't guarantee that more than one of them is random." Figure that out.
— W. H. Press et al.[3]
References
- ^ Entacher, Karl (June 2000). "A collection of classical pseudorandom number generators with linear structures - advanced version". Retrieved 2009-01-13.
- ^ Marsaglia, George (1968). "Random Numbers Fall Mainly in the Planes". Proc National Academy of Sciences. 61 (1): 25–28. doi:10.1073/pnas.61.1.25.
- ^ a b Press, William H.; et al. (1992). Numerical Recipes in Fortran 77: The Art of Scientific Computing (2nd ed.). ISBN 0-521-43064-X.
{{cite book}}
: Explicit use of et al. in:|author=
(help) - ^ ref. 7 of http://portal.acm.org/citation.cfm?id=363827
- ^ Donald E. Knuth (1998). The Art of Computer Programming. Vol. 22 (3rd ed.). Boston: Addison-Wesley.