A Linear Congruential Generator (LCG) represents 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.
The generator is defined by the recurrence relation:
where Xn is the sequence of pseudorandom values, and
are integer constants that specify the generator.
The period of a general LCG is at most m, and for some choices of a much less than that. Provided that c is nonzero, the LCG will have a full period for all seed values if and only if:
While LCGs are capable of producing decent pseudorandom numbers, this is extremely sensitive to the choice of the parameters c, m, and a.
Historically, poor choices had led to ineffective implementations of LCGs. A particularly illustrative example of this is RANDU which was widely used in the early 1970s and lead to many results which are currently being questioned because of the use of this poor LCG.
Parameters in common use
The most efficient LCGs have an m equal to a power of 2, most often m = 232 or m = 264, because this allows the modulus operation to be computed by merely truncating all but the rightmost 32 or 64 bits. The following table lists the parameters of LCGs in common use, including built-in rand() functions in runtime libraries of various compilers.
As shown above, LCG's do not always use all of the bits in the values they produce. The Java implementation produces 48 bits with each iteration but only returns the 32 most significant bits from these values. This is because the higher-order bits have longer periods than the lower order bits (see below). LCG's that use this technique produce much better values than those that do not.
Advantages and disadvantages of LCGs
LCGs are fast and require minimal memory (typically 32 or 64 bits) to retain state. This makes them valuable for simulating multiple independent streams.
LCGs should not be used for applications where high-quality randomness is critical.
Full article ▸