Linear congruential generators (LCGs) 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. It is, however, well known that the properties of this class of generator are far from ideal. If higher quality random numbers are needed, and sufficient memory is available (~ 2 KBytes), then the Mersenne twister algorithm is a preferred choice. A pseudorandom number generator (PRNG) is an algorithm that generates a sequence of numbers which are not truly random. ... In mathematics, computing, linguistics, and related disciplines, an algorithm is a procedure (a finite set of well-defined instructions) for accomplishing some task which, given an initial state, will terminate in a defined end-state. ... The Mersenne twister is a pseudorandom number generator developed in 1997 by Makoto Matsumoto (松本 眞) and Takuji Nishimura (西村 拓士). It provides for fast generation of very high quality pseudorandom numbers, having been designed specifically to rectify many of the flaws found in older algorithms. ...

LCGs are defined by the recurrence relation:

Where V_n is the sequence of random values and A, B and M are generator-specific integer constants. mod is the modulo operation. In computing, the modulo operation finds the remainder of division of one number by another. ...

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:

1. B 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

4. M > max (A, B, V₀)

5. A > 0, B > 0

hyperplanes of a linear congruential generator in three dimensions

While LCGs are (theoretically) capable of producing decent pseudorandom numbers, this is extremely sensitive to the choice of B, M and A. Historically, poor choices had led to ineffective implementations of LCG's. A particularly illustrative example of this is RANDU which was widely used in the early 1970's and resulted in many results that are currently in doubt because of the use of this poor LCG (Press, William H., et al. (1992)). 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. This is due to serial correlation between successive values of the sequence V_n. The spectral test, which is a simple test of an LCG's quality, is based on this fact. In mathematics, the integers a and b are said to be coprime or relatively prime if and only if they have no common factor other than 1 and −1, or equivalently, if their greatest common divisor is 1. ... In number theory, the prime factors of a positive integer are the prime numbers that divide into that integer exactly, without leaving a remainder. ... Image File history File links Lcg_3d. ... Image File history File links Lcg_3d. ... RANDU is an infamous linear congruential pseudorandom number generator which has been used since the 1960s. ... A hyperplane is a concept in geometry. ...

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 m representation of the output sequence, where m^k = M for some integer k, repeats with at most period mⁿ. In mathematics, a power of two is any of the nonnegative integer powers of the number two; in other words, two times itself a certain number of times. ...

The Mersenne twister both runs faster than and generates higher-quality deviates than almost any LCG, so only LCGs with M equal to a power of 2, most often M = 2³² or M = 2⁶⁴, could make a good efficiency to performance tradeoff. These are the fastest-evaluated of all random number generators; a common Mersenne twister implementation uses it to generate seed data. Numerical Recipes in C advocates a generator of this form with: The Mersenne twister is a pseudorandom number generator developed in 1997 by Makoto Matsumoto (松本 眞) and Takuji Nishimura (西村 拓士). It provides for fast generation of very high quality pseudorandom numbers, having been designed specifically to rectify many of the flaws found in older algorithms. ...

A = 1664525, B = 1013904223, M = 2³²

Neither this, nor any other LCG should 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. 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 high-order bits of an LCG may well suffice. The low-order bits of LCGs should never be relied on for any degree of randomness whatsoever. Indeed, it is not generally realised that the above generator popularized by Numerical Recipes produces alternately odd and even results! Monte Carlo methods are algorithms for solving various kinds of computational problems by using random numbers (or more often pseudo-random numbers), as opposed to deterministic algorithms. ... A cryptographically secure pseudo-random number generator (CSPRNG) is a pseudo-random number generator (PRNG) with properties that make it suitable for use in cryptography. ... video game consoles A video game console is an interactive entertainment computer. ... Numerical Recipes is the generic term for the following books on algorithms and numerical analysis, all by William Press, Saul Teukolsky, William Vetterling and Brian Flannery: Numerical Recipes in C++. The Art of Scientific Computing, ISBN 0-521-75033-4. ...

See also

• Full Cycle
• Inversive congruential generator

Full Cycle Recordings is a record label based in Bristol, England specialising in drum and bass. ... Inversive congruential generators are a type of nonlinear congruential pseudorandom number generator, which use the modular multiplicative inverse (if it exists) to generate the next number in a sequence. ...

References

• 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).

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

Donald Knuth at a reception for the Open Content Alliance. ... Numerical Recipes is the generic term for the following books on algorithms and numerical analysis, all by William Press, Saul Teukolsky, William Vetterling and Brian Flannery: Numerical Recipes in C++. The Art of Scientific Computing, ISBN 0-521-75033-4. ...

External Links

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