Linear congruential generators

A linear congruential generator (LCG) is a type of non-cryptographic pseudo-random number generator (PRNG) that is simple enough to implement one in minutes.

Definition

LCGs use the recursion
$$x_{n + 1} = \text{mod}_m(ax_n + c)$$

The output is generated from the sequence $x_1, x_2, ...$ by truncating the $b$ least significant bits.

In the recursion, $x_0$ is the seed, $m$ is the modulus, $a$ is the multiplier, and $c$ is the increment. We will focus exclusively on the case where $m$ is a power of two, because this case can be efficiently implemented in binary arithmetic.

When $c = 0$, the generator is also called a multiplicative congruential generator (MCG) or sometimes a Lehmer congruential generator. We will consider LCGs and MCGs separately. Since the properties of a properly parameterized LCG is the same for any increment $c \neq 0$ we can set $c = a$.

Properties

The entire state space of an LCG has size $m$, which means that an LCG has maximum period $m$. The $k$th bit of a sequence $x_1, x_2$ generated by an LCG will have period $2^k$ at most. This can be easily understood by noting that the $k$ least significant bits form an LCG with $m = 2^k$. This is the reason that we discard the $b$ least significant bits: After discarding, the output will have period $2^b$ in its least significant bit.

It can be shown that any MCG with $m = 2^n$ is equivalent to an LCG with $m = 2^{n - 2}$. So, for an MCG with modulus $m = 2^n$, the maximum period is $2^{n - 2}$, and the period of the $k$th bit of the output is $2^{n - b - 2}$. The maximum period is achieved when the seed $x_0$ is odd, and the multiplier is of the form $a = \pm 3 \pmod 8$.

For many multipliers, LCGs will fail a particular statistical test called the spectral test. However, if we use a large modulus, and cherry-pick a multiplier that does well on the spectral test, LCGs pass even stringent statistical tests.

Since conventional knowledge is that LCGs and MCGs are bad, and LLMs will advise against using them, I feel the need to post some references to justify my claim that it is OK to use LCGs in most cases:

• From the wikipedia page on linear congruential generators: “A[n] LCG with large enough state can pass even stringent statistical tests; a modulo-$2^{64}$ 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 […]”.
• Melissa O’Neill has has reported that “[PractRand] will require more than three hundred years of testing to detect statistical flaws [in a 96-bit LCG].”.
• John D. Cook ran the NIST statistical test suite and reported: “[An LCG] passed nearly all the tests, even though some more sophisticated generators failed some of the same tests.”.

Suggested parameters

The following parameters are suggested by Melissa O’Neill.

• For a 32-bit MCG, use $m = 2^{96}$, $b = 64$, $a = 63684207872218969504639112949$.
• For a 64-bit MCG, use $m = 2^{128}$, $b = 64$, $a = 63788880824840432877499191278319602189$.
• For a 32-bit LCG, use $m = 2^{96}$, $b = 64$, $a = 61124247442928732736190063229$.
• For a 64-bit LCG, use $m = 2^{128}$, $b = 64$, $a = 199967246047888932297834045878657099405$.

Implementation

These are simple header-only C++ implementations of 32- and 64-bit MCGs and LCGs using the parameters from the previous section. You need to #include <cstdint> to use them.

32-bit MCG

class MCG32 {
public:
	// seed needs to be odd for a maximum period
	MCG(unsigned __int128 seed) : mState(seed | 1) {
		next();
	}

	uint64_t next() {
		mState = mState * multiplier;
		return mState >> 64;
	}

private:
	static const __uint128_t multiplier =
	    ((__uint128_t)0xcdc65792ULL << 64) |
	    0x6766e07328a856f5ULL;
	unsigned __int128 mState;
};

64-bit MCG

class MCG64 {
public:
	// seed needs to be odd for a maximum period
	MCG(unsigned __int128 seed) : mState(seed | 1) {
		next();
	}

	uint64_t next() {
		mState = mState * multiplier;
		return mState >> 64;
	}

private:
	static const __uint128_t multiplier =
	    ((__uint128_t)0x2ffd4aa4540b972cULL << 64) |
	    0x007c03e5caca8a0dULL;
	unsigned __int128 mState;
};

32-bit LCG

class LCG32 {
public:
	MCG(unsigned __int128 seed) : mState(seed) {
		next();
	}

	uint64_t next() {
		mState = mState * multiplier + multiplier;
		return mState >> 64;
	}

private:
	static const __uint128_t multiplier =
	    ((__uint128_t)0xc580caddULL << 64) |
	    0x754f7336d2eaa27dULL;
	unsigned __int128 mState;
};

64-bit LCG

class LCG64 {
public:
	MCG(unsigned __int128 seed) : mState(seed) {
		next();
	}

	uint64_t next() {
		mState = mState * multiplier + multiplier;
		return mState >> 64;
	}

private:
	static const __uint128_t multiplier = ((__uint128_t)
	    0x96704a6bb5d2c4fbULL << 64) |
	    0x3aa645df0540268dULL;
	unsigned __int128 mState;
};