Lehmer random number generator

From Wikipedia, the free encyclopedia
  (Redirected from Lehmer RNG)
Jump to: navigation, search

The Lehmer random number generator[1] (named after D. H. Lehmer), sometimes also referred to as the Park–Miller random number generator (after Stephen K. Park and Keith W. Miller), is a variant of linear congruential generator (LCG) that operates in multiplicative group of integers modulo n. A general formula of a random number generator (RNG) of this type is:

X_{k+1} = g \cdot X_k~~\bmod~~n

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 X0 is co-prime to n.

Parameters in common use[edit]

In 1988, Park and Miller[2] suggested a Lehmer RNG with particular parameters n = 231 − 1 = 2,147,483,647 (a Mersenne prime M31) and g = 75 = 16,807 (a primitive root modulo M31), now known as MINSTD. Although MINSTD was later criticized by Marsaglia and Sullivan (1993),[3] it is still in use today (in particular, in CarbonLib and C++11's minstd_rand0). Park, Miller and Stockmeyer responded to the criticism (1993),[4] saying:

Given the dynamic nature of the area, it is difficult for nonspecialists to make decisions about what generator to use. "Give me something I can understand, implement and port... it needn't be state-of-the-art, just make sure it's reasonably good and efficient." Our article and the associated minimal standard generator was an attempt to respond to this request. Five years later, we see no need to alter our response other than to suggest the use of the multiplier a = 48271 in place of 16807.

This revised constant is used in C++11's minstd_rand random number generator.

ZX81 and its successors use the Lehmer RNG with parameters n = 216 + 1 = 65,537 (a Fermat prime F4) and g = 75 (a primitive root modulo F4). [5] The CRAY random number generator RANF is a Lehmer RNG with n = 248 and g = 44,485,709,377,909.[6] The GNU Scientific Library includes several random number generators of the Lehmer form, including MINSTD, RANF, and the infamous IBM random number generator RANDU.[6]

Relation to LCG[edit]

While the Lehmer 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 Lehmer RNG, the initial seed X0 must be coprime 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 Lehmer RNG. In contrast to LCG, the maximum period of the Lehmer 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 Xk in \mathbb{Z}_n represent linear congruential sequence modulo Euler totient \varphi(n).

Sample C99 code[edit]

Using C code, the Lehmer generator using the "popular pair" of parameters mentioned above can be written as follows:

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

As the product of two 32 bit integers may overflow, the cast to uint64_t is necessary.

References[edit]

  1. ^ 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. 
  2. ^ Stephen K. Park and Keith 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. 
  3. ^ Marsaglia, George and Sullivan, Stephen (1993). "Technical correspondence". Communications of the ACM 36 (7): 105–110. doi:10.1145/159544.376068. 
  4. ^ Stephen K. Park and Keith W. Miller and Paul K. Stockmeyer (1988). "Technical Correspondence". Communications of the ACM 36 (7): 105–110. doi:10.1145/159544.376068. 
  5. ^ Vickers, Steve. "Chapter 5 - Functions". ZX81 Basic Programming. Sinclair Research Ltd. The ZX81 uses p=65537 & a=75 [...]  Note the ZX81 manual incorrectly states that 65537 is a Mersenne prime that equals 216-1. The ZX Spectrum manual fixed that and correctly states that it is a Fermat prime that equals 216+1.
  6. ^ a b GNU Scientific Library: Other random number generators