(algorithm)
Definition: A class of algorithms that are pseudo-random number generators. The next number is generated from the current one by rn+1 = (A × rn + B) mod M, where A and M are relatively prime numbers.
Generalization (I am a kind of ...)
pseudo-random number generator.
Note: When implemented in software, A and B may be chosen so as to have integer overflow on nearly every step, and therefore have a less predictable sequence and avoid the mod operation. The low-order bits tend to be less random than high-order bits. This is improved by discarding some of the low-order bits. Therefore, the range of random numbers is less than the range of the integer used in the computation.
Better algorithms are available, but they are more complex.
Author: BB
Karl Entacher's thorough review and comparison of many linear congruential generators.
If you have suggestions, corrections, or comments, please get in touch with Paul Black.
Entry modified 1 February 2012.
HTML page formatted Mon Feb 2 13:10:39 2015.
Cite this as:
Bob Bockholt, "linear congruential generator", in
Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 1 February 2012. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/linearCongruentGen.html