Linear congruential Generator (LCG) Parameters of Good Quality

Background

Multiplicative congruential generators (MCGs) and linear congruential generators (LCGs) are a common algorithm for implementing a pseudo-random random number generator (PRNG). They take the form of:
x_n = ax_n−1 (mod m) (MCG)
x_n = ax_n−1 + c (mod m) (LCG),
where x is the sequence of outputs (x₀ is the so-called seed, which I assume is a term you are familiar with), a is the multiplier, c is the increment and m is the modulus.

In 1999, Pierre L’Ecuyer presented a paper entitled Tables of Linear Congruential Generators of Different Sizes and Good Lattice Structure that was published in volume 68(225) of Mathematics of Computation, pp. 249–260 (doi:10.1090/S0025-5718-99-00996-5). However, there have been significant errata affecting the most useful part, the tables of good MCG and LCG parameters. Neither are PDFs particularly accessible nor are errata obvious to find, so I will be summarizing the parts relevant for those who just want a working MCG or LCG.

There are two major kinds of generators that L’Ecuyer looked at: Those with prime m and those with m as a power of two. With prime m, no increment c is necessary. However, with m being a power of two—and for performance reasons this is often interesting—, the maximum period with no increment can be achieved with a = 5 (mod 8) for a period of m/4; by adding an (odd) increment c, you can get the full period of m. However, in any case, with an LCG with a modulus that is a power of two, you must use only the upper bits as the lower bits have a small period. Additionally, if using no increment, the seed must be odd with a power of two. In summary:

m is prime

no increment; difficult to make uniform random numbers out of

m is a power of two and using no increment

toss lower bits, ideally at least 32;
seed must be odd

m is a power of two and using increment

toss lower bits, ideally at least 32;
increment must be odd

For implementation reasons, only Mersenne primes and pseudo-Mersenne primes (2^e − f, where f is very small [pseudo-Mersenne prime] or f = 1 [Mersenne prime]) are considered for prime moduli. Details on how to implement this are widely available.

I do not recommend using an LCG or MCG and instead suggest, wherever possible, the use of the xo(ro)shiro family or LXM generators. But practical necessity sometimes makes an LCG or MCG unavoidable.

Historical note: Guy L. Steele Jr. and Sebastino Vigna have presented a different set of multipliers and performed an exhaustive search for all numbers up to 35 bits in their paper Computationally easy, spectrally good multipliers for congruential pseudorandom number generators, published in volume 52(2) of Journal of: Software: Practice and Experience, pp. 443–458 (doi:10.1002/spe.3030). These seem preferable over L’Ecuyer’s multipliers as they could benefit from modern computational power to explore the search space. However, my post only provides the parameters in L’Ecuyer’s paper because the errata are numerous and significant, so using them without a consolidated list is inconvenient.

Tables incorporating the errata

In these tables, the M value roughly means whether the multipliers that are good for small, medium and large dimensions. The best M value in a class is emphasized. You generally want the one with the best for M₃₂.

The a* value is the multiplicative inverse of a and generates the same sequence, just in reverse.

Table for prime m

Use x_n = ax_n−1 (mod m).

Data also available as comma-separated values (CSV).

Table for prime m and small multiplication result

Use x_n = ax_n−1 (mod m).

This table gives parameters that ensure that the product of a multiplied by m − 1 is less than 2⁵³, allowing safe implementation with IEEE floating point numbers (e. g. JavaScript's sole number type). Values numbers of class for 2²⁷ and lower are not given as this constraint is also met by the prime m table above for all multipliers (except for a ≥ 67108883 for m = 2²⁷ − 39). No a* values are given, which would all be too great.

Data also available as comma-separated values (CSV).

Table for m as a power of two and odd c

Use x_n = ax_n−1 + c (mod m).

No a* values are given as the increment prevents the reverse sequence by just using a modular multiplicative inverse.

Data also available as comma-separated values (CSV).

Table for m as a power of two c = 0

Use x_n = ax_n−1 (mod m).

Avoid these generators; see above. Either use an increment or a prime modulus instead. For completeness relating to the original paper, I still list the values here.

Data also available as comma-separated values (CSV).