Linear congruential generator
|
|
Linear congruential generators (LCGs) represent one of the oldest and best-known pseudorandom number generator algorithms. The theory behind them is easy to understand, and they are easily implemented and fast. It is, however, well known that the properties of this class of generator are far from ideal. If higher quality random numbers are needed, and sufficient memory is available (~ 2 KBytes), then the Mersenne twister algorithm is a preferred choice.
LCGs are defined by the recurrence relation:
- <math>V_{j+1} \equiv A \times V_j + B \pmod M<math>
Where Vn is the sequence of random values and A, B and M are generator-specific integer constants. See modular arithmetic for an explanation of the "mod M" notation.
The period of a general LCG is at most M, and in most cases less than that. The following three rules are necessary and sufficient conditions to achieve a full period of length M:
- 1. B and M must be relatively prime
- 2. For each prime p such that p divides M, A-1 is a multiple of p
- 3. A-1 is a multiple of 4
LCGs tend to exhibit some severe defects. For instance, if an LCG is used to choose points in an n-dimensional space, triples of points will lie on, at most, M1/n hyperplanes. This is due to serial correlation between successive values of the sequence Vn. The spectral test, which is a relatively easy test of an LCG's quality, is based on this fact.
A further problem of LCGs is that the lower-order bits of the generated sequence have a far shorter period than the sequence as a whole if M is set to a power of 2. In general, the nth least significant digit in the base m representation of the output sequence, where <math>m^k = M<math> for some integer k, repeats with at most period <math>m^n<math>.
Today, with the advent of the Mersenne twister, which both runs faster than and generates higher-quality deviates than almost any LCG, only LCGs with M equal to a power of 2, most often M = 232 or M = 264, make sense at all. These are the fastest-evaluated of all random number generators; a common Mersenne twister implementation uses it to generate seed data. Numerical Recipes in C advocates a generator of this form with:
- A = 1664525, B = 1013904223, M = 232
Neither this, nor any other LCG should be used for applications where high-quality randomness is critical. For example, it is not suitable for a Monte Carlo simulation because of the serial correlation (among other things). Nevertheless, LCGs may be the only option in some cases. For instance, in an embedded system, the amount of memory available is often very severely limited. Similarly, in an environment such as a video game console taking a small number of high-order bits of an LCG may well suffice.
For more information, consult:
A thorough discussion: Stephen K. Park and Keith W. Miller Random Number Generators: Good Ones Are Hard To Find Communications of the ACM, 31(10):1192-1201, 1988.
A more simplistic explanation:Linear Congruential Number Generators (http://www.math.rutgers.edu/~greenfie/currentcourses/sem090/pdfstuff/jp.pdf)