Definitions
Nearby Words

# 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_\left\{k+1\right\} = X_kcdot g~~bmod~~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^\left\{31\right\}-1=2147483647$ (a Mersenne prime $M_\left\{31\right\}$) and $g=16807$ (a primitive root modulo $M_\left\{31\right\}$). 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^\left\{16\right\}+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^\left\{48\right\}$ and $g=44485709377909$. Another popular pair of parameters is $n = 2^\left\{32\right\}-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\left\{Z\right\}_n$ represent linear congruential sequence modulo Euler totient $phi\left(n\right)$.

## 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

Search another word or see Park–Miller RNGon Dictionary | Thesaurus |Spanish