A Study of the Most Famous Random Number Generator | by Ayoub Omari | Sep, 2022

Explaining the linear congruential generator and its weaknesses

If you have been programming for a while, chances are you have worked on random number generation in some project or another.

I didn’t question how random number generation works the first time I worked with random numbers in a program. I have been assuming that the generated numbers are truly drawn randomly.

However, the question could be raised by a simple thought.

Any program is made up of a specific sequence of instructions. If we provide an input to it, we get the same output each time we provide that input. We call this property determinism. Trying to generate random numbers using a program is trying to get random behavior from a deterministic tool, which is kind of a paradox…

Realizing that it is not possible to get a truly random number generator with a computer, researchers had an idea: It is sufficient to get sequences that seem random.

After all, no one is able to tell if a sequence of numbers was drawn randomly or not. There is always a non-zero probability to get any sequence of numbers we can think of, provided that each of those numbers falls within the range this generator is working on.

For example, a random number generator may return the same number a thousand times in a row. The probability is indeed low, but it is still possible.

A regular person won’t be satisfied with a random number generator that returns the same number several times in a row, or with sequences such as:

• 3 -> 4 -> 5 -> 6 -> 7 -> …
• 2 -> 6 -> 18 -> 54 -> 162 -> …
• 2 -> 4 -> 16 -> 256 -> 65536 -> …

What do such examples have in common that make us unsatisfied? They have an easy-to-detect pattern.

It may surprise you, but did you know that most random generators aren’t more complicated than that ?

Instead of returning the increment of the previous number, its multiplication by 3, or its square, the most famous random number generator, which had been widely used until recently, does the following:

Where a and b are chosen constants. M defines the range of numbers we generate.

With this function, we are able to generate sequences such as:

72 -> 5 -> 614 -> 37 -> 140 -> …

As users, we don’t see any pattern in this sequence. So we may say it is random. If someone is familiar enough with the function, this can be a pattern for them to say that the sequence was probably drawn using this specific function.

This random number generator is called the Linear Congruential Generator.

In the following sections, we shall discuss how bad this random generator is, and attempt to improve it.

Is the linear congruential generator a good random generator ?

To evaluate the quality of random number generators, we will use two visualizations: Bitmap and Random Walk. Both of these methods evaluate specific bits of the numbers we generate.

Let’s first choose a linear generator by fixing a, b, and M. It has been proven that the best linear congruential generators satisfy the following conditions:

1. M and b are relatively prime
2. a-1 is divisible by all prime factors of M
3. a-1 is divisible by 4 if M is divisible by 4

Let’s choose the values that had been used in C language for the function rand (which obviously satisfy the conditions above).

The bitmap of the most significant bit gives the following:

Each generated number Xn+1 is represented by a pixel. If the most significant bit of the number is equal to 0, the pixel is black, otherwise it’s white.

The bitmap is indeed random and we don’t have any pattern.

Let’s see what a 2D random walk gives.

With a 2D random walk, we evaluate 2 bits at the same time. Two bits give four possible values. Based on the value, we move in one of the four directions up, down, left, right. Here we are evaluating the two most significant bits (31st and 30th) of Xn+1.

The random walk looks really random and shows no pattern. Shall we say this is a good random number generator ? Not before evaluating the other bits.

Let’s evaluate a bit in the middle, such as the 15th. Following are the bitmap and the random walk for that bit.

This time it’s a different story, and we can see some patterns. In the bitmap, you can see some lines of the same color. In the random walk, you can see that the shape is symmetric on a diagonal axis and repeats forever… This is not good news for supposedly “random” behavior.

Let’s see what happens with the first bit (the rightmost bit).

Well, there is nothing random in these two results. If you zoom in the bitmap, you find alternating black and white pixels. In the random walk, it goes up, down, right, left and repeats forever. Why does that happen ?

The first bit is the parity bit, the one that indicates if the number is even or odd. If you take any sequence with this random number generator you will see that every odd number is followed by an even number, and every even number is followed by an odd number, like the sequence we saw earlier in this article. Hence, the first bit is alternating between the values 0 and 1. This explains the bitmap figure. For the random walk, the direction is determined by the first and second bit. As we will see in the next sections, there is a cycle after four steps.

If you do the same for the remaining bits, you will conclude that the pattern gets clearer and the randomness gets worse as we go to the right in the bits.

In the following section, we will study why this happens.

With the linear congruential generator, the first bit of X{n+1} is solely determined by the first bit of a, Xn, and b. For odd a and odd b, we get from the equation:

• if Xn is odd then X{n+1} is even
• if Xn is even then X{n+1} is odd

This justifies the result of the bitmap in the last section.

So maybe a different parity of a or b may solve our issue with the first bit ? Let’s see that in the following table.

From this table, only odd a and odd b are able to give us all possible numbers. Hence, we can’t do better than the result we got. We say that the period of the first bit is of length 2, because we have a sequence of length 2 that repeats forever.

Similarly, let’s examine the conditions on a and b that allow to get all possible values of the second bit. This time, the second bit of X{n+1} depends both on the first and the second bit of a, b, and Xn. The following table gives the sequence of values of the first two bits of X{n+1} depending on the first two bits of a and b.

Here as well, the sequence of the first two bits repeats itself. But only a ending with 01 gives all possible four values for X{n+1} before the cycle. Hence, that’s a new condition on a to get all possible values of the first two bits.

1. a and b should be odd
2. a should end with 01.
   In other words a mod 4 = 1.
   In other words a-1 should be a multiple of 4

We retrieve here one of the conditions of the theorem we saw earlier about optimal linear congruential generators (condition n°3). Because M=2³¹ is a multiple of 4, a-1 should be a multiple of 4.

What we’ve got so far:

• 1st bit: period of length 2
• 2nd bit: period of length 4

And if you iterate on the following bits, you get similarly:

• 3rd bit: period of length 8 at most
• 4th bit: period of length 16 at most
• ….
• 31st bit: period has length 2³¹ at most

Moreover, the two conditions we fixed above on the first two bits of a and b are sufficient to get the maximum period for all the remaining bits. This is why the condition “a-1 should be a multiple of 4 if M is a multiple of 4” appears in the final theorem.

To sum up, because they have a greater period, the upper bits get better randomness than the lower bits.

From the previous section, we understand the reason why the ith bit has a period of length 2^i. It’s because the ith bit of X{n+1} depends only on the first i bits of Xn. 2^i is the maximum number of combinations we can get with i bits.

So, we need a way to make the first bit depend on the other bits as well. Addition and multiplication only propagate bits to the left. Is there any operation that propagates bits to the right ? A division !

For example, if we want to make the 1st bit of X{n+1} depend on the 3rd bit of Xn. We divide Xn by 4, this is equivalent to shifting the bits of Xn two steps to the right.

So let’s update our linear congruential generator with this:

Let’s now see if this improves the randomness of the 1st bit.

This greatly improves the randomness of the 1st bit! There are some patterns in the bitmap (see the black dots), but it’s much better than alternating black and white.

Let’s see if we are still good with the 31st bit.

Well, not so good, now we get patterns in the bitmap (see the black dots), and you can see a shape repeating indefinitely in the random walk.

We can try another amount to shift with. For that, I wrote a program that returns the period for different shift amounts. Here is the result:

No amount gives the maximum period of 2³¹. Hence, this form of functions does not solve our issue without impacting the period of the random number generator.

It’s not easy to study variants of the linear congruential generator that solve the issue of lower bits and at the same time achieve a maximum period length. The tuning of a and b has been proven for aX+b and any variant should be studied well enough so as not to fall into a short cycle. I tried different versions of the function such as the following. Each time I get a shorter cycle:

• X{n+1} = (aXn + b + X >> 2) mod M
• X{n+1} = (aXn + b + sum i from 1 to N (X >> i)) mod M
• X{n+1} = (aXn + b + xor i from 1 to N (X >> i)) mod M
• X{n+1} = (aXn + b + sum of N-1 most significant bits) mod M
• …

If you give it a try, perhaps you may find a variant that solves both period and lower bits issues!

It was quite surprising for me to find out that one of the most famous random number generators was not random at all. In this article, we have seen how the linear congruential generator fails to get seemingly random sequences for the lower bits of the numbers it generates. We also used two methods of visualizations that help evaluate a random number generator with the naked eye.

Today, there are more advanced random generators that don’t have the issue of lower bits such as Mersenne Twister, which is not as simple as the linear congruential generator, but would definitely deserve the time to understand how it works.