Park–Miller random number generator

From Wikipedia, the free encyclopedia

The Park–Miller random number generator (or 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 generator (RNG) of this type is:

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

Contents 1 Parameters in common use 2 Relation to LCG 3 Sample C99 code 4 References

[edit] Parameters in common use

Park and Miller suggested particular values n = 2³¹ − 1 = 2147483647 (a Mersenne prime M₃₁) and g = 16807 (a primitive root modulo M₃₁). The Park–Miller RNG with these parameters is a build-in RNG in Apple CarbonLib. ZX Spectrum uses the Park–Miller RNG with parameters n = 2¹⁶ + 1 = 65537 (a Fermat prime F₄) and g=75 (a primitive root modulo F₄). GNU Scientific Library uses the Park–Miller RNG with n = 2⁴⁸ and g = 44485709377909. Another popular pair of parameters is n = 4294967291 and g = 279470273.

[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 difference from 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 C99 code, this is written as follows:

#include <stdint.h>

uint32_t lcg_rand (uint32_t a)
{
    return ((uint64_t)a * 279470273) % 4294967291;
}

[edit] References

• 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.  (alternative link to PDF)
• 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.  (alternative link to PDF)
• Steve Park Random Number Generators
• Park-Miller-Carta Pseudo-Random Number Generator
• GNU Scientific Library: Other random number generators