# Linear congruential generators

Linear congruential generators (LCGs) 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 given the first terms .

## Implementation

An LCG uses the recursion

to generate a sequence of pseudorandom numbers. The parameters consist of

• The seed
• The multiplier
• The increment
• The modulus

Typically, is a power of two (ofen , , , or ). In this case, the least significant bits have a period of . For this reason, the lower (least significant) bits of the terms should be discarded, depending on how large a period is acceptable. This is sometimes called a truncated LCG.

When the generator is called a multiplicative congruential generator or a Lehmer generator. When 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 , the following multipliers are “good”:

For (note that this is not enough to pass most statistical tests):

Bits Multiplier
16 0x72ed
32 0x93d765dd

For (note that this is not enough to pass most statistical tests):

Bits Multiplier
32 0xe817fb2d
64 0xf1357aea2e62a9c5

For :

Bits Multiplier
64 0xdefba91144f2b375

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

• MCGs have a maximum possible period of
• The bit in position of an MCG has period (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 .

#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 , the following multipliers are “good”:

For (note that this is not enough to pass most statistical tests):

Bits Multiplier
16 0xd9f5
32 0x915f77f5

For (note that this is not enough to pass most statistical tests):

Bits Multiplier
32 0xf9b25d65
64 0xd1342543de82ef95

For :

Bits Multiplier
64 0xfc0072fa0b15f4fd
128 0xdb36357734e34abb0050d0761fcdfc15

An LCG generates a sequence where the bits up to position have a period of .

### Example implementation

This is a simple header-only C++ implementation of an LCG using the 64-bit constant for . 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

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 […]”.