Park–Miller random number generator

From Wikipedia, the free encyclopedia

The Park–Miller random number generator also known as the Lehmer random number generator is a variant of linear congruential generator that operates in multiplicative group of integers modulo n. A general formula of a random number generator (RNG) of this type is:

where the modulus n is a prime number or a power of a prime number, the multiplier g is an element of high multiplicative order modulo n (e.g., a primitive root modulo n), and the seed X₀ is co-prime to n.

[edit] Parameters in common use

In 1988, Park and Miller ^[1] suggested RNG with particular parameters n=2³¹−1 = 2,147,483,647 (a Mersenne prime M₃₁) and g=16,807 (a primitive root modulo M₃₁), now known as MINSTD. Despite that MINSTD was later criticized by Marsaglia and Sullivan, ^[2] it is still in use today (in particular, in CarbonLib).

ZX Spectrum uses the Park–Miller RNG with parameters n=2¹⁶+1 = 65,537 (a Fermat prime F₄) and g=75 (a primitive root modulo F₄). The CRAY random number generator RANF is a Park–Miller RNG with n=2⁴⁸ and g=44,485,709,377,909. ^[3] Another popular pair of parameters is n=2³²−5 = 4,294,967,291 and g=279,470,273.

The GNU Scientific Library includes several random number generators of the Park–Miller form, including MINSTD, RANF, and the infamous IBM random number generator RANDU. ^[3]

[edit] Relation to LCG

While the Park–Miller RNG can be viewed as a particular case of the linear congruential generator with c=0, it is a special case that implies certain restrictions and properties. In particular, for the Park–Miller RNG, the initial seed X₀ must be co-prime to the modulus n that is not required for LCGs in general. The choice of the modulus n and the multiplier g is also more restrictive for the Park–Miller RNG. In contrast to LCG, the maximum period of the Park–Miller RNG equals n−1 and it is such when n is prime and g is a primitive root modulo n.

On the other hand, the discrete logarithms (to base g or any primitive root modulo n) of X_k in represent linear congruential sequence modulo Euler totient φ(n).

[edit] Sample C99 code

Using C code, this is written as follows:

unsigned long lcg_rand(unsigned long a)
{
    return (a * 279470273UL) % 4294967291UL;
}

[edit] References

1. ^ S.K. Park and K.W. Miller (1988). "Random Number Generators: Good Ones Are Hard To Find". Communications of the ACM 31 (10): 1192–1201. doi:10.1145/63039.63042. http://www.firstpr.com.au/dsp/rand31/p1192-park.pdf. 
2. ^ Crawford, Diane (1993). "Technical correspondence". Communications of the ACM 36 (7): 105–110. doi:10.1145/159544.376068. 
3. ^ ^{a b} GNU Scientific Library: Other random number generators

• W.H. Payne, J.R. Rabung, T.P. Bogyo (1969). "Coding the Lehmer pseudo-random number generator". Communications of the ACM 12 (2): 85–86. doi:10.1145/362848.362860. http://www.firstpr.com.au/dsp/rand31/p85-payne.pdf. 
• Steve Park Random Number Generators
• Park-Miller-Carta Pseudo-Random Number Generator