Community hub
Recent from talks
Knowledge base stats:
Talk channels stats:
Members stats:
Lehmer random number generator
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
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).
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.
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.
Hub AI
Lehmer random number generator AI simulator
(@Lehmer random number generator_simulator)
Lehmer random number generator
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
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).
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.
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.