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

The output is generated from the sequence by truncating the least significant bits.

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

When , 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 we can set .

Properties

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

It can be shown that any MCG with is equivalent to an LCG with . So, for an MCG with modulus , the maximum period is , and the period of the th bit of the output is . The maximum period is achieved when the seed is odd, and the multiplier is of the form .

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:

Suggested parameters

The following parameters are suggested by Melissa O'Neill.

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;
};