Linear congruential generator

The theory behind them is relatively easy to understand, and they are easily implemented and fast, especially on computer hardware which can provide modular arithmetic by storage-bit truncation.

[1]: 4- When c ≠ 0, a mathematician would call the recurrence an affine transformation, not a linear one, but the misnomer is well-established in computer science.

[6] While LCGs are capable of producing pseudorandom numbers which can pass formal tests for randomness, the quality of the output is extremely sensitive to the choice of the parameters m and a.

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.

A second disadvantage of a prime modulus is that it is awkward to convert the value 1 ≤ x < m to uniform random bits.

Choosing m to be a power of two, most often m = 232 or m = 264, produces a particularly efficient LCG, because this allows the modulus operation to be computed by simply truncating the binary representation.

[15][16] This form may be used with any m, but only works well for m with many repeated prime factors, such as a power of 2; using a computer's word size is the most common choice.

If m were a square-free integer, this would only allow a ≡ 1 (mod m), which makes a very poor PRNG; a selection of possible full-period multipliers is only available when m has repeated prime factors.

If a pseudorandom number less than r is desired, ⌊rX/m⌋ is a much higher-quality result than X mod r. Unfortunately, most programming languages make the latter much easier to write (X % r), so it is very commonly used.

The generator is not sensitive to the choice of c, as long as it is relatively prime to the modulus (e.g. if m is a power of 2, then c must be odd), so the value c=1 is commonly chosen.

For example, the Java implementation operates with 48-bit values at each iteration but returns only their 32 most significant bits.

LCGs are fast and require minimal memory (one modulo-m number, often 32 or 64 bits) to retain state.

The fact that people have been lulled for so many years into using them with such small moduli can be seen as a testament to the strength of the technique.

[37] For related reasons, any PRNG should have a period longer than the square of the number of outputs required.

Carelessly chosen multipliers will usually have far fewer, widely spaced planes, which can lead to problems.

Another flaw specific to LCGs is the short period of the low-order bits when m is chosen to be a power of 2.

Similarly, in an environment such as a video game console taking a small number of high-order bits of an LCG may well suffice.

LCGs should be evaluated very carefully for suitability in non-cryptographic applications where high-quality randomness is critical.

(We would prefer them to be completely coprime, but a prime modulus implies an even period, so there must be a common factor of 2, at least.)

Marsaglia's add-with-carry and subtract-with-borrow PRNGs with a word size of b=2w and lags r and s (r > s) are equivalent to LCGs with a modulus of br ± bs ± 1.

A permuted congruential generator begins with a power-of-2-modulus LCG and applies an output transformation to eliminate the short period problem in the low-order bits.

[41] Lagged Fibonacci generators also fall into this category; although they use arithmetic addition, their period is ensured by an LFSR among the least-significant bits.

It is easy to detect the structure of a linear-feedback shift register with appropriate tests[42] such as the linear complexity test implemented in the TestU01 suite; a Boolean circulant matrix initialized from consecutive bits of an LFSR will never have rank greater than the degree of the polynomial.

Adding a non-linear output mixing function (as in the xoshiro256** and permuted congruential generator constructions) can greatly improve the performance on statistical tests.

A powerful technique for generating high-quality pseudorandom numbers is to combine two or more PRNGs of different structure; the sum of an LFSR and an LCG (as in the KISS or xorwow constructions) can do very well at some cost in speed.