A Research of the Most Well-known Random Quantity Generator | by Ayoub Omari | Sep, 2022

Explaining the linear congruential generator and its weaknesses

When you’ve got been programming for some time, likelihood is you’ve gotten labored on random quantity technology in some mission or one other.

I didn’t query how random quantity technology works the primary time I labored with random numbers in a program. I’ve been assuming that the generated numbers are really drawn randomly.

Nevertheless, the query might be raised by a easy thought.

Any program is made up of a selected sequence of directions. If we offer an enter to it, we get the identical output every time we offer that enter. We name this property determinism. Making an attempt to generate random numbers utilizing a program is attempting to get random conduct from a deterministic software, which is sort of a paradox…

Realizing that it isn’t doable to get a very random quantity generator with a pc, researchers had an concept: It’s enough to get sequences that appear random.

In any case, nobody is ready to inform if a sequence of numbers was drawn randomly or not. There may be all the time a non-zero likelihood to get any sequence of numbers we are able to consider, supplied that every of these numbers falls throughout the vary this generator is engaged on.

For instance, a random quantity generator might return the identical quantity a thousand instances in a row. The likelihood is certainly low, however it’s nonetheless doable.

An everyday particular person received’t be happy with a random quantity generator that returns the identical quantity a number of instances in a row, or with sequences corresponding to:

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

What do such examples have in frequent that make us unhappy? They’ve an easy-to-detect sample.

It might shock you, however do you know that almost all random turbines aren’t extra difficult than that ?

As a substitute of returning the increment of the earlier quantity, its multiplication by 3, or its sq., essentially the most well-known random quantity generator, which had been extensively used till lately, does the next:

The place a and b are chosen constants. M defines the vary of numbers we generate.

With this perform, we’re in a position to generate sequences corresponding to:

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

As customers, we don’t see any sample on this sequence. So we might say it’s random. If somebody is acquainted sufficient with the perform, this is usually a sample for them to say that the sequence was most likely drawn utilizing this particular perform.

This random quantity generator is known as the Linear Congruential Generator.

Within the following sections, we will focus on how dangerous this random generator is, and try to enhance it.

Is the linear congruential generator a superb random generator ?

To judge the standard of random quantity turbines, we are going to use two visualizations: Bitmap and Random Stroll. Each of those strategies consider particular bits of the numbers we generate.

Let’s first select a linear generator by fixing a, b, and M. It has been confirmed that the very best linear congruential turbines fulfill the next circumstances:

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

Let’s select the values that had been utilized in C language for the perform rand (which clearly fulfill the circumstances above).

The bitmap of essentially the most vital bit provides the next:

Every generated quantity Xn+1 is represented by a pixel. If essentially the most vital little bit of the quantity is the same as 0, the pixel is black, in any other case it’s white.

The bitmap is certainly random and we don’t have any sample.

Let’s see what a 2D random stroll provides.

With a 2D random stroll, we consider 2 bits on the similar time. Two bits give 4 doable values. Based mostly on the worth, we transfer in one of many 4 instructions up, down, left, proper. Right here we’re evaluating the 2 most vital bits (thirty first and thirtieth) of Xn+1.

The random stroll seems to be actually random and reveals no sample. Shall we embrace this can be a good random quantity generator ? Not earlier than evaluating the opposite bits.

Let’s consider a bit within the center, such because the fifteenth. Following are the bitmap and the random stroll for that bit.

This time it’s a unique story, and we are able to see some patterns. Within the bitmap, you’ll be able to see some strains of the identical coloration. Within the random stroll, you’ll be able to see that the form is symmetric on a diagonal axis and repeats without end… This isn’t excellent news for supposedly “random” conduct.

Let’s see what occurs with the primary bit (the rightmost bit).

Effectively, there may be nothing random in these two outcomes. For those who zoom within the bitmap, you discover alternating black and white pixels. Within the random stroll, it goes up, down, proper, left and repeats without end. Why does that occur ?

The primary bit is the parity bit, the one which signifies if the quantity is even or odd. For those who take any sequence with this random quantity generator you will notice that each odd quantity is adopted by a fair quantity, and each even quantity is adopted by an odd quantity, just like the sequence we noticed earlier on this article. Therefore, the primary bit is alternating between the values 0 and 1. This explains the bitmap determine. For the random stroll, the route is set by the primary and second bit. As we are going to see within the subsequent sections, there’s a cycle after 4 steps.

For those who do the identical for the remaining bits, you’ll conclude that the sample will get clearer and the randomness will get worse as we go to the fitting within the bits.

Within the following part, we are going to examine why this occurs.

With the linear congruential generator, the primary little bit of X{n+1} is solely decided by the primary little 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 results of the bitmap within the final part.

So possibly a unique parity of a or b might clear up our difficulty with the primary bit ? Let’s see that within the following desk.

From this desk, solely odd a and odd b are in a position to give us all doable numbers. Therefore, we are able to’t do higher than the outcome we obtained. We are saying that the interval of the primary bit is of size 2, as a result of we now have a sequence of size 2 that repeats without end.

Equally, let’s look at the circumstances on a and b that permit to get all doable values of the second bit. This time, the second little bit of X{n+1} relies upon each on the primary and the second little bit of a, b, and Xn. The next desk provides the sequence of values of the primary two bits of X{n+1} relying on the primary two bits of a and b.

Right here as effectively, the sequence of the primary two bits repeats itself. However solely a ending with 01 provides all doable 4 values for X{n+1} earlier than the cycle. Therefore, that’s a brand new situation on a to get all doable values of the primary two bits.

1. a and b needs to be odd
2. a ought to finish with 01.
   In different phrases a mod 4 = 1.
   In different phrases a-1 needs to be a a number of of 4

We retrieve right here one of many circumstances of the concept we noticed earlier about optimum linear congruential turbines (situation n°3). As a result of M=2³¹ is a a number of of 4, a-1 needs to be a a number of of 4.

What we’ve obtained to date:

• 1st bit: interval of size 2
• 2nd bit: interval of size 4

And in the event you iterate on the next bits, you get equally:

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

Furthermore, the 2 circumstances we mounted above on the primary two bits of a and b are enough to get the utmost interval for all of the remaining bits. This is the reason the situation “a-1 needs to be a a number of of 4 if M is a a number of of 4” seems within the remaining theorem.

To sum up, as a result of they’ve a higher interval, the higher bits get higher randomness than the decrease bits.

From the earlier part, we perceive the rationale why the ith bit has a interval of size 2^i. It’s as a result of the ith little bit of X{n+1} relies upon solely on the primary i bits of Xn. 2^i is the utmost variety of combos we are able to get with i bits.

So, we’d like a solution to make the primary bit rely on the opposite bits as effectively. Addition and multiplication solely propagate bits to the left. Is there any operation that propagates bits to the fitting ? A division !

For instance, if we wish to make the 1st little bit of X{n+1} rely on the third little bit of Xn. We divide Xn by 4, that is equal to shifting the bits of Xn two steps to the fitting.

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

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

This drastically improves the randomness of the first bit! There are some patterns within the bitmap (see the black dots), nevertheless it’s significantly better than alternating black and white.

Let’s see if we’re nonetheless good with the thirty first bit.

Effectively, not so good, now we get patterns within the bitmap (see the black dots), and you’ll see a form repeating indefinitely within the random stroll.

We are able to strive one other quantity to shift with. For that, I wrote a program that returns the interval for various shift quantities. Right here is the outcome:

No quantity provides the utmost interval of 2³¹. Therefore, this type of features doesn’t clear up our difficulty with out impacting the interval of the random quantity generator.

It’s not straightforward to review variants of the linear congruential generator that clear up the difficulty of decrease bits and on the similar time obtain a most interval size. The tuning of a and b has been confirmed for aX+b and any variant needs to be studied effectively sufficient in order to not fall into a brief cycle. I attempted completely different variations of the perform corresponding to the next. Every 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 vital bits) mod M
• …

For those who give it a strive, maybe you might discover a variant that solves each interval and decrease bits points!

It was fairly shocking for me to search out out that one of the well-known random quantity turbines was not random in any respect. On this article, we now have seen how the linear congruential generator fails to get seemingly random sequences for the decrease bits of the numbers it generates. We additionally used two strategies of visualizations that assist consider a random quantity generator with the bare eye.

Right now, there are extra superior random turbines that don’t have the difficulty of decrease bits corresponding to Mersenne Tornado, which isn’t so simple as the linear congruential generator, however would positively deserve the time to grasp the way it works.