Park–Miller random number generator

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:

: $$X_{k+1} = X_kcdot g~~mod~~n

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

Parameters in common use

Park and Miller suggested particular values $$n=2^{31}-1=2147483647 (a Mersenne prime $$M_{31}) and $$g=16807 (a primitive root modulo $$M_{31}). The Park–Miller RNG with these parameters (known as "MINSTD") is a build-in RNG in Apple CarbonLib. ZX Spectrum uses the Park–Miller RNG with parameters $$n=2^{16}+1=65537 (a Fermat prime $$F_4) and "g=75" (a primitive root modulo $$F_4). The CRAY random number generator RANF uses a Park–Miller RNG with $$n=2^{48} and $$g=44485709377909. [http://www.gnu.org/software/gsl/manual/html_node/Other-random-number-generators.html GNU Scientific Library: Other random number generators] ] Another popular pair of parameters is $$n = 2^{32}-5 =4294967291 and $$g=279470273.

The GNU Scientific Library includes several random number generators of the Park-Miller form, including Park-Miller random number generator "MINSTD", the CRAY random number generator "RANF", and the infamous IBM random number generator "RANDU".

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_0 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 $$mathbb{Z}_n represent linear congruential sequence modulo Euler totient $$phi(n).

Sample C99 code

Using C99 code, this is written as follows:

#include

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

References

* ( [http://www.firstpr.com.au/dsp/rand31/p85-payne.pdf alternative link to PDF] )
* ( [http://www.firstpr.com.au/dsp/rand31/p1192-park.pdf alternative link to PDF] )
* Steve Park [http://www.cs.wm.edu/~va/software/park/ Random Number Generators]
* [http://www.firstpr.com.au/dsp/rand31/ Park-Miller-Carta Pseudo-Random Number Generator]