The Lehmer random number generator (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 type of linear congruential generator (LCG) that operates in multiplicative group of integers modulo n. The general formula is
X k + 1 = a ⋅ X k mod m , {\displaystyle X_{k+1}=a\cdot X_{k}{\bmod {m}},}
where the modulus m is a prime number or a power of a prime number, the multiplier a is an element of high multiplicative order modulo m (e.g., a primitive root modulo n), and the seed X0 is coprime to m. Other names are multiplicative linear congruential generator (MLCG) and multiplicative congruential generator (MCG).
Parameters in common use In 1988, Park and Miller suggested a Lehmer RNG with particular parameters m = 231 − 1 = 2,147,483,647 (a Mersenne prime M31) and a = 75 = 16,807 (a primitive root modulo M31), now known as MINSTD. Although MINSTD was later criticized by Marsaglia and Sullivan (1993), 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), 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. The Sinclair ZX81 and its successors use the Lehmer RNG with parameters m = 216 + 1 = 65,537 (a Fermat prime F4) and a = 75 (a primitive root modulo F4). The CRAY random number generator RANF is a Lehmer RNG with the power-of-two modulus m = 248 and a = 44,485,709,377,909. The GNU Scientific Library includes several random number generators of the Lehmer form, including MINSTD, RANF, and the infamous IBM random number generator RANDU.
Choice of modulus Most commonly, the modulus is chosen as a prime number, making the choice of a coprime seed trivial (any 0 < X0 < m will do). This produces the best-quality output, but introduces some implementation complexity, and the range of the output is unlikely to match the desired application; converting to the desired range requires an additional multiplication. Using a modulus m which is a power of two makes for a particularly convenient computer implementation, but comes at a cost: the period is at most m/4, and the lower bits have periods shorter than that. This is because the lowest k bits form a modulo-2k generator all by themselves; the higher-order bits never affect lower-order bits. The values Xi are always odd (bit 0 never changes), bits 2 and 1 alternate (the lower 3 bits repeat with a period of 2), the lower 4 bits repeat with a period of 4, and so on. Therefore, the application using these random numbers must use the most significant bits; reducing to a smaller range using a modulo operation with an even modulus will produce disastrous results. To achieve this period, the multiplier must satisfy a ≡ ±3 (mod 8), and the seed X0 must be odd. Using a composite modulus is possible, but the generator must be seeded with a value coprime to m, or the period will be greatly reduced. For example, a modulus of F5 = 232 + 1 might seem attractive, as the outputs can be easily mapped to a 32-bit word 0 ≤ Xi − 1 < 232. However, a seed of X0 = 6700417 (which divides 232 + 1) or any multiple would lead to an output with a period of only 640. Another generator with a composite modulus is the one recommended by Nakazawa & Nakazawa:
m = 134265023 × 134475827 = 18055400005099021 ≈ 254 a = 7759097958782935 (any of ±a±1 (mod m) will do as well) As both factors of the modulus are less than 232, it is possible to maintain the state modulo each of the factors, and construct the output value using the Chinese remainder theorem, using no more than 64-bit intermediate arithmetic. A more popular implementation for large periods is a combined linear congruential generator; combining (e.g. by summing their outputs) several generators is equivalent to the output of a single generator whose modulus is the product of the component generators' moduli. and whose period is the least common multiple of the component periods. Although the periods will share a common divisor of 2, the moduli can be chosen so that is the only common divisor and the resultant period is (m1 − 1)(m2 − 1)···(mk − 1)/2k−1. One example of this is the Wichmann–Hill generator.
Relation to LCG 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 m, which is not required for LCGs in general. The choice of the modulus m and the multiplier a is also more restrictive for the Lehmer RNG. In contrast to LCG, the maximum period of the Lehmer RNG equals m − 1, and it is such when m is prime and a is a primitive root modulo m. On the other hand, the discrete logarithms (to base a or any primitive root modulo m) of Xk in Z m {\displaystyle \mathbb {Z} _{m}} represent a linear congruential sequence modulo the Euler totient φ ( m ) {\displaystyle \varphi (m)} .
… excerpt ends here. Continue reading the full article.
