Linear congruential generator

A linear congruential generator (LCG) represent one of the oldest and best-known pseudorandom number generator algorithms. [" [http://demonstrations.wolfram.com/LinearCongruentialGenerators/ Linear Congruential Generators] " by Joe Bolte, The Wolfram Demonstrations Project.] The theory behind them is easy to understand, and they are easily implemented and fast.

The generator is defined by the recurrence relation:

:

where X_n is the sequence of random values, and

: the "modulus": the "multiplier": the "increment" (the special case of $c=0$ corresponds to Park–Miller RNG): the "seed" or "start value"

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. The LCG will have a full period if and only if:

:1. $,c$ and $,m$ are relatively prime,:2. $,a\; -\; 1$ is divisible by all prime factors of $,m$,:3. $,a\; -\; 1$ is a multiple of 4 if $,m$ is a multiple of 4 [Donald E. Knuth, "The Art of Computer Programming", Volume 2, 3rd Edition, pp. 17-19] .

While LCGs are capable of producing decent pseudorandom numbers, this is extremely sensitive to the choice of the coefficients "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 resulted in many results that are currently in doubt because of the use of this poor LCG [Press, William H., "et al." (1992)] .

If a linear congruential generator is seeded with a character and then iterated once, the result is a simple classical cipher called an affine cipher; this cipher is easily broken by standard frequency analysis.

LCGs in common use

The most efficient LCGs have an "m" equal to a power of 2, most often "m = 2³²" or "m = 2⁶⁴", 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 various compilers.

Advantages and disadvantages of LCGs

LCGs should not 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). They should also not be used for cryptographic applications; see cryptographically secure pseudo-random number generator for more suitable generators.

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, m^1/n hyperplanes (Marsaglia's Theorem, developed by George Marsaglia). This is due to serial correlation between successive values of the sequence X_n. The spectral test, which is a simple 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 "n"th least significant digit in the base "b" representation of the output sequence, where $b^k\; =\; m$ for some integer "k", repeats with at most period $b^n$.

Nevertheless, LCGs may be a good option. 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. The low-order bits of LCGs when m is a power of 2 should never be relied on for any degree of randomness whatsoever. Indeed, simply substituting 2^n for the modulus term reveals that the low order bits go through very short cycles. In particular, any full-cycle LCG when m is a power of 2 will produce alternately odd and even results!

Comparison with other PRNGs

If higher quality random numbers are needed, and sufficient memory is available (~ 2 kilobytes), then the Mersenne twister algorithm is a preferred choice. The Mersenne twister generates higher-quality deviates than almost any LCG. A common Mersenne twister implementation, interestingly enough, uses an LCG to generate seed data.

The random number generators of certain commercially available software packages should not be confused with LCG's as they operate on a completely different principle. Namely, many eliminate the "linear" aspect of the generation. As such, the "repeat" times are much longer and the distribution does not suffer from the planing problem described above.

ee also

* Park-Miller RNG
* Full cycle
* Inversive congruential generator

References

** cite journal | author = S.K. Park and K.W. Miller |title=Random Number Generators: Good Ones Are Hard To Find |journal=Communications of the ACM |year=1988 |volume=31 |issue=10 |pages=1192–1201 |url=http://portal.acm.org/citation.cfm?id=63042 |doi=10.1145/63039.63042

* D. E. Knuth. "The Art of Computer Programming", Volume 2: "Seminumerical Algorithms", Third Edition. Addison-Wesley, 1997. ISBN 0-201-89684-2. Section 3.2.1: The Linear Congruential Method, pp.10–26.

*

* Press, William H., "et al." (1992). "Numerical Recipes in Fortran 77: The Art of Scientific Computing", 2nd edition. ISBN 0-521-43064-X.

* (in this paper, efficient algorithms are given for inferring sequences produced by certain pseudo-random number generators).

External links

* The simulation [http://www.vias.org/simulations/simusoft_lincong.html Linear Congruential Generator] visualizes the correlations between the pseudo-random numbers when manipulating the parameters.