Linear congruential generator

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:

$X_{n+1} \equiv \left( a X_n + c \right)~~\pmod{m}$

where $X$ is the sequence of pseudorandom values, and

$m,\, 0<m$ — the "modulus"

$a,\,0 < a < m$ — the "multiplier"

$c,\,0 \le c < m$ — the "increment"

$X_0,\,0 \le X_0 < m$ — the "seed" or "start value"

are integer constants that specify the generator. If c = 0, the generator is often called a multiplicative congruential method, or Lehmer RNG. If c ≠ 0, the generator is called a mixed congruential method.

Period length

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:

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.

These three requirements are referred to as the Hull-Dobell Theorem. 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 led 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 = 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 runtime libraries of various compilers.

Source	m	a	c	output bits of seed in rand() / Random(L)
Numerical Recipes	232	1664525	1013904223
Borland C/C++	232	22695477	1	bits 30..16 in rand(), 30..0 in lrand()
glibc (used by GCC)	231	1103515245	12345	bits 30..0
ANSI C: Watcom, Digital Mars, CodeWarrior, IBM VisualAge C/C++	231	1103515245	12345	bits 30..16
Borland Delphi, Virtual Pascal	232	134775813	1	bits 63..32 of (seed * L)
Microsoft Visual/Quick C/C++	232	214013 (343FD16)	2531011 (269EC316)	bits 30..16
Microsoft Visual Basic (6 and earlier)	224	1140671485 (43FD43FD16)	12820163 (C39EC316)
RtlUniform from Native API	231 − 1	2147483629 (7FFFFFED16)	2147483587 (7FFFFFC316)
Apple CarbonLib	231 − 1	16807	0	see MINSTD
MMIX by Donald Knuth	264	6364136223846793005	1442695040888963407
Newlib	264	6364136223846793005	1	bits 63...32
VAX's MTH$RANDOM, old versions of glibc	232	69069	1
Java's java.util.Random	248	25214903917	11	bits 47...16
LC53 in Forth	232 − 5	232 − 333333333	0

As shown above, LCGs do not always use all of the bits in the values they produce. For example, the Java implementation operates with 48-bit values at each iteration but returns only their 32 most significant bits. This is because the higher-order bits have longer periods than the lower order bits (see below). LCGs that use this truncation technique produce statistically 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.

Hyperplanes of a linear congruential generator in three dimensions

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. 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 tend to exhibit some severe defects. For instance, if an LCG is used to choose points in an n-dimensional space, the 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 nth 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ⁿ.

Nevertheless, LCGs may be a good option. For instance, in an embedded system, the amount of memory available is often 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ⁿ 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 provides a vastly longer period (2¹⁹⁹³⁷ − 1) and variate uniformity. The Mersenne twister generates higher-quality deviates than almost any LCG.^{[citation needed]} A common Mersenne twister implementation, interestingly enough, uses an LCG to generate seed data.

A Linear Feedback Shift Register PRNG can be implemented with essentially the same amount of memory and produces a stream of pseudorandom numbers with better randomness qualities^{[citation needed]} when considering streams of bits, albeit with a bit more computation.

See also

• Full cycle
• Inversive congruential generator
• Multiply-with-carry
• Lehmer RNG (sometimes called the Park-Miller RNG)
• Combined Linear Congruential Generator

References

• S.K. Park and K.W. Miller (1988). "Random Number Generators: Good Ones Are Hard To Find". Communications of the ACM 31 (10): 1192–1201. 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.
• P. L'Ecuyer (1999). "Tables of Linear Congruential Generators of Different Sizes and Good Lattice Structure". Mathematics of Computation 68 (225): 249–260. doi:10.1090/S0025-5718-99-00996-5. 
• Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007), "Section 7.1.1. Some History", Numerical Recipes: The Art of Scientific Computing (3rd ed.), New York: Cambridge University Press, ISBN 978-0-521-88068-8 
• Gentle, James E., (2003). Random Number Generation and Monte Carlo Methods, 2nd edition, Springer, ISBN 0-387-00178-6.
• Joan Boyar (1989). "Inferring sequences produced by pseudo-random number generators". Journal of the ACM 36 (1): 129–141. doi:10.1145/58562.59305.  (in this paper, efficient algorithms are given for inferring sequences produced by certain pseudo-random number generators).

External links

• The simulation Linear Congruential Generator visualizes the correlations between the pseudo-random numbers when manipulating the parameters.
• Security of Random Number Generation: An Annotated Bibliography
• Linear Congruential Generators post to sci.math
• The "Death of Art" computer art project at Goldstein Technologies LLC, uses an LCG to generate 33,554,432 images
• P. L'Ecuyer and R. Simard, ``TestU01: A C Library for Empirical Testing of Random Number Generators, May 2006, Revised November 2006, ACM Transactions on Mathematical Software, 33, 4, Article 22, August 2007.