LCGs are defined by the recurrence relation:
Where V_{n} is the sequence of random values and A, B and M are generatorspecific constants. See modular arithmetic for an explanation of the "mod M" notation.
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 ndimensional space, triples of points will lie on, at most, M^{1/n} hyperplanes. This is due to serial correlation between successive values of the sequence V_{n}.
A further problem of LCGs is that the lowerorder 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 higherquality deviates than almost any LCG, only LCGs with M = 2^{32} (or 2^{64}) make sense at all (these are the fastestevaluated of all random number generators). Numerical Recipes in C advocates a generator of this form with:
Neither this, nor any other LCG should be used for applications where highquality 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 highorder bits of an LCG may well suffice.
Search Encyclopedia

Featured Article
