Linear congruential generator

A linear congruential generator (LCG) 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. The generator is defined by the recurrence relation:

<math>X_{n+1} = \left( a X_n + c \right) \bmod m</math>

where X_n is the sequence of random values, and

<math> \,0 < m </math> the "modulus"

<math> \,0 \le a < m </math> the "multiplier"

<math> \,0 \le c < m </math> the "increment"

<math> \,0 \le X_0 < m </math> the "seed" or "start value"

are integer constants that specify the generator. The period of a general LCG is at most m, and in most cases less than that. The LCG will have a full period if and only if:

1. <math>\,c</math> and <math>\,m</math> are relatively prime,

2. <math>\,a - 1</math> is divisible by all prime factors of <math>\,m</math>,

3. <math>\,a - 1</math> is a multiple of 4 if <math>\,m</math> is a multiple of 4^[1].

While LCGs are capable of producing decent pseudorandom numbers, this is extremely sensitive to the choice of 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)). The most efficient LCGs have an m equal to a power of 2, most often m = 2³² or m = 2⁶⁴.

Example LCGs

Numerical Recipes in C advocates a generator of this form with:

a = 1664525, c = 1013904223, m = 2³²

Borland Turbo C uses these values (while using only the 16 upper bits of the seed - without the MSB):

a = 22695477, c = 1 , m = 2³²

Another usable LCG, which uses 64-bit arithmetic to generate a 32-bit number, is as follows:

<math>X_{n+1} = \left(279470273 \times X_n\right) \bmod 4294967291</math>

Using C99 code, this is written as follows:

#include <stdint.h>
uint32_t gen(unsigned int a) {
        uint64_t z;
        z = a;
        z *= 279470273; 
        z %= 4294967291U;
        a = z;
        return a;
}

Advantages and disadvantages of LCGs

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. 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). 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 <math>b^k = m</math> for some integer k, repeats with at most period <math>m^n</math>. 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, the above generator popularized by Numerical Recipes produces 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 both runs faster than and generates higher-quality deviates than almost any LCG. A common Mersenne twister implementation, interestingly enough, uses a LCG to generate seed data.

See also

• Full cycle
• Inversive congruential generator

References

1. ^ Donald E. Knuth, The Art of Computer Programming, Volume 2, 3rd Edition, pp. 17-19

• A thorough discussion: Stephen K. Park and Keith W. Miller, Random Number Generators: Good Ones Are Hard To Find, Communications of the ACM, 31(10):1192-1201, 1988
• A more simplistic explanation: Linear Congruential Number Generators
• 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, "Tables of Linear Congruential Generators of Different Sizes and Good Lattice Structure", Mathematics of Computation 68:225, 249–260 (1999). Available online at Citeseer.
• Press, William H., et al. (1992). Numerical Recipes in Fortran 77: The Art of Scientific Computing, 2nd edition. ISBN 0-521-43064-X.
• ACM Press, Joan Boyar, In this paper, efficient algorithms are given for inferring sequences produced by certain pseudo-random number generators: [1]

External links

• The simulation Linear Congruential Generator visualizes the correlations between the pseudo-random numbers when manipulating the parameters.