Evolution of random number generators

The previous post showed that the bits of prime powers look kinda chaotic. When you plot them, they form a triangular shape because the size of the numbers is growing. The numbers are growing geometrically, so their binary representations are growing linearly. Here's the plot for powers of 5:

You can crop the triangle so that you just see a rectangular portion of it, things look less regular. If we look at powers of p modulo a power of 2, say 2³², then we're chopping off the left side of the triangle.

Suppose we don't start with 1, but start with some other number, call it a seed, and multiply by 5 every time. Would we get a chaotic pattern? Yes, and we have just invented the congruential random number generator. These RNGs have the form

x_n+1 = a x_n mod m

The RNG we implicitly described above would have a = 5 and m = 2³². This is not a good choice of a and m, but it's on to something. We can use different values of multiplier and modulus to make a decent RNG.

The RANDU random number generator, commonly used in the 1960's, used a = 65539 and m = 2³¹. This turned out to have notoriously bad statistical properties. We can see this with a small modification of the code used to produce the plot above.

 def out(s): s = s.replace('1', chr(0x2588)) s = s.replace('0', ' ') print(s) a, m = 65539, 2**31 x = 7 for i in range(32): x = a * x % m s = format(x, '32b') out(s)

Here's the plot.

The pattern on the right side looks like a roll of film. This shows that the lowest order bits are very regular. You can also see that we need to start with a large seed: starting with 7 created the large triangular holes at the top of the image. There are other patterns in the image that are hard to describe, but you get the sense something is not right, especially when you compare this image to a better alternative.

A much better choice of parameters is multiplier a = 48271 and modulus m = 2³¹ -1. These are the parameters in the MINSTD random number generator. Here's a plot of its bits, also starting with seed 7.

The MINSTD generator is much better than RANDU, and adequate for some applications, but far from state of the art. You could do better by using a much larger multiplier and a modulus on the order of 2⁶⁴ or 2¹²⁸.

You could do even better by adding a permutation step to your congruential generator. That's the idea behind the PCG (permuted congruential generator) family of random number generators. These generators pass all the standard statistical tests with flying colors.

There are many other approaches to random number generation, but this post shows one thread of historical development, how hypothetically someone could go from noticing that prime powers have chaotic bit patterns to inventing PCG.

Related posts

• Inverse congruential RNGs
• Shrinking generators
• ChaCha with fewer rounds
• RNG testing

The post Evolution of random number generators first appeared on John D. Cook.