Random number generator algorithm mod#
If a double-width product is not available, Schrage's method, also called the approximate factoriation method, may be used to compute ax mod m, but this comes at the cost: (It also requires the multiplication by d to produce a product larger than e bits, as mentioned above.) However, as long as d 2 < 2 e, the first reduction will produce a value in the range required for the preceding case of two reduction steps to apply. Finally subtracting the temporary offset produces the desired value.īegin by assuming that we have a partially reduced value y which is bounded so 0 ≤ y m, then it is possible for the first reduction step to produce a sum greater than 2 m = 2 e+1−2 d, which is too large for the final reduction step. The solution is to temporarily add d so that the range of possible values is d through 2 e−1, and reduce values larger than e bits in a way that never generates representations less than d. The fundamental challenge of a modulus like 2 32−5 lies in ensuring that we produce only one representation for values such as 1 ≡ 2 32−4. Most commonly, the modulus is chosen as a prime number, making the choice of a coprime seed trivial (any 0 1, conditional subtraction can also be avoided, but the procedure is more intricate.
Random number generator algorithm generator#
The GNU Scientific Library includes several random number generators of the Lehmer form, including MINSTD, RANF, and the infamous IBM random number generator RANDU. The CRAY random number generator RANF is a Lehmer RNG with the power-of-two modulus m = 2 48 and a = 44,485,709,377,909. The Sinclair ZX81 and its successors use the Lehmer RNG with parameters m = 2 16+1 = 65,537 (a Fermat prime F 4) and a = 75 (a primitive root modulo F 4). This revised constant is used in C++11's minstd_rand random number generator. 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. 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.
"Give me something I can understand, implement and port. Given the dynamic nature of the area, it is difficult for nonspecialists to make decisions about what generator to use. Park, Miller and Stockmeyer responded to the criticism (1993), saying: 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). In 1988, Park and Miller suggested a Lehmer RNG with particular parameters m = 2 31 − 1 = 2,147,483,647 (a Mersenne prime M 31) and a = 7 5 = 16,807 (a primitive root modulo M 31), now known as MINSTD.