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:
- Vj+1 = A · Vj + B (mod M)
The period of a general LCG is at most M, and very often less than that. In addition, they tend to exhibit 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.
A further problem of LCGs is that the lower-order bits of the generated sequence may cycle with a far shorter period than the sequence as a whole, particularly if M is set to a power of 2.
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
