# Linear congruential generators

Linear congruential generators (*LCG*s) are the fastest and simplest type of pseudorandom number generator (PRNG). They have somewhat of a bad name, because there have been some implementations that used bad parameters. However, with properly chosen parameters, LCGs should not have any statistical problems. However, it should be noted that LCGs are not a cryptographically secure pseudorandom number generator, and are predictable. This means that there are ways to predict the rest of a pseudorandom sequence $x_{n+1},x_{n}$ given the first $n$ terms $x_{1},x_{2},...,x_{n}$.

## Implementation

An LCG uses the recursion

$x_{n+1}=(ax_{n}+c)modm$to generate a sequence $x_{1},x_{2},...$ of pseudorandom numbers. The parameters consist of

- The
*seed*$x_{0}$ - The
*multiplier*$a$ - The
*increment*$c$ - The
*modulus*$m$

Typically, $m$ is a power of two (ofen $2_{32}$, $2_{64}$, $2_{96}$, or $2_{128}$). In this case, the $k$ least significant bits have a period of $2_{k}$. For this reason, the lower (least significant) bits of the terms $x_{1},x_{2},...$ should be discarded, depending on how large a period is acceptable. This is sometimes called a *truncated* LCG.

When $c=0$ the generator is called a *multiplicative congruential generator* or a *Lehmer generator*. When $c=0$ we call the generator a *mixed congruential generator*. Sometimes, the term LCG refers specifically to a mixed congruential generator and the abbreviation MCG is used to refer to a multiplicative congruential generator. I will follow this convention from now on as well.

Both for LCGs and MCGs, it is extremely important to pick good parameters, since the properties of the pseudorandom sequence depends on it.

## MCGs

MCGs with a modulus that is a power of two should have an odd seed. According to [1], the following multipliers are “good”:

For $m=2_{32}$ (note that this is not enough to pass most statistical tests):

Bits | Multiplier |
---|---|

16 | 0x72ed |

32 | 0x93d765dd |

For $m=2_{64}$ (note that this is not enough to pass most statistical tests):

Bits | Multiplier |
---|---|

32 | 0xe817fb2d |

64 | 0xf1357aea2e62a9c5 |

For $m=2_{128}$:

Bits | Multiplier |
---|---|

64 | 0xdefba91144f2b375 |

128 | 0xaadec8c3186345282b4e141f3a1232d5 |

Some semi-interesting facts about MCGs with a modulus that is a power of two:

- MCGs have a maximum possible period of $4m $
- The bit in position $k$ of an MCG has period $2_{k}$ (so the least significant bit is constant, bit 1 is alternating, etc.)

### Example implementation

This is a simple header-only C++ implementation of an MCG using the 64-bit constant for $m=2_{128}$.

```
#include <cstdint>
class MCG {
public:
MCG(unsigned __int128 seed) : mState(seed | 1) {
// when the seed is zero, the first term in the sequence will be zero
// (this is only the case when the multiplier is 64-bit)
next();
}
uint64_t next() {
mState = mState * multiplier;
return mState >> 64;
}
private:
static const uint64_t multiplier = 0xdefba91144f2b375;
unsigned __int128 mState;
};
```

## LCGs

For LCGs, any seed can be used. The increment can be any odd number. Note that when the multiplier is smaller than the modulus (e.g. half the bit size of the modulus), the first term in the sequence is zero whenever the seed is one. To avoid this, we can skip the first term of the sequence.

According to [1], the following multipliers are “good”:

For $m=2_{32}$ (note that this is not enough to pass most statistical tests):

Bits | Multiplier |
---|---|

16 | 0xd9f5 |

32 | 0x915f77f5 |

For $m=2_{64}$ (note that this is not enough to pass most statistical tests):

Bits | Multiplier |
---|---|

32 | 0xf9b25d65 |

64 | 0xd1342543de82ef95 |

For $m=2_{128}$:

Bits | Multiplier |
---|---|

64 | 0xfc0072fa0b15f4fd |

128 | 0xdb36357734e34abb0050d0761fcdfc15 |

An LCG generates a sequence where the bits up to position $k$ have a period of $2_{k}$.

### Example implementation

This is a simple header-only C++ implementation of an LCG using the 64-bit constant for $m=2_{128}$. The multiplier is also used as the increment. Note that an 128-bit unsigned integer is used, which requires a GCC-specific compiler extension. So the code is not portable (though it should be easy-to-port to any other compiler with support for 128-bit integers).

```
#include <cstdint>
class LCG {
public:
LCG(unsigned __int128 state) : mState(state) {
// when the seed is zero, the first term in the sequence will be zero
// (this is only the case when the multiplier is 64-bit)
next();
}
uint64_t next() {
mState = mState * multiplier + multiplier;
return mState >> 64;
}
private:
static const uint64_t multiplier = 0xfc0072fa0b15f4fd;
unsigned __int128 mState;
};
```

## Statistical properties

As I mentioned before, the sequences generated by LCGs and MCGs are of high quality, given that the output is truncated and the parameters are chosen properly.

The quality of PRNGs is commonly used by running statistical testsuites on them. Popular ones are

- TestU01, with the “BigCrush” testsuite being the most stringent one
- PractRand
- Diehard
- Dieharder
- NIST Statistical Test Suite
- ENT
- gjrand
- RaBiGeTe

People have tried running these on LCGs, here are some testimonies I found.

From the wikipedia page on linear congruential generators: “A[n] LCG with large enough state can pass even stringent statistical tests; a modulo-2 LCG which returns the high 32 bits passes TestU01’s SmallCrush suite and a 96-bit LCG passes the most stringent BigCrush suite.”

Mellissa O’Neill, author of the PCG PRNG, writes that an 128-bit MCG passes PractRand. In On Vigna’s PCG critique, she mentions “A simple truncated 128-bit LCG passes all standard statistical tests once we get up to 128 bits […]”.

## References and further reading

[2] ‘Linear congruential generator’, wikipedia.

For further reading on PRNGs I recommend the blog of the author of PCG, Melissa O’Neill. The following posts are especially interesting: