A Truly Horrible Random Number Generator

I needed a bad random number generator for an illustration, and chose RANDU, possibly the worst random number generator that was ever widely deployed. Donald Knuth comments on RANDU in the second volume of his magnum opus.

When this chapter was first written in the late 1960s, a truly horrible random number generator called RANDU was commonly used on most of the world's computers.

This generator starts with an odd seed x₀ and generates subsequent values via

x_n+1 = 65539 x_n mod 2³¹

I needed to generate 8-bit numbers, and I took the lowest eight bits of each value from RANDU (to be fair, the highest 8 bits would have been better, but my goal was to find a bad RNG, so I used the lowest).

To demonstrate the generator's (lack of) quality I made a histogram of sorts with a 16 by 16 grid, one cell for each possible 8-bit number. I generated a large number of samples and plotted the grid. Here's what I got:

Here's what I get with a better random number generator:

I was looking for something bad, but I didn't realize RANDU was that bad. The white stripes represent the generated values and the black stripes values that are never generated. So out of 256 possible 8-bit numbers, this generator only ever outputs 64 of them (I used 33 as my seed; I might have gotten different vertical stripes if I had chosen a different seed, but I'd still get stripes). Also, the frequencies of the values it does take on have suspiciously little variation.

You can see the pattern of values RANDU takes on by printing out the first few generated values in hex:

    0x63
    0x29
    0x7b
    0x71
    0x53
    0xf9
    0xeb
    0xc1

The last hex digit cycles 3, 9, b, 1, 3, 9, b, 1, ... producing only four possible values.

We could prove the statements empirically demonstrated above by noting that

x_n = 65539ⁿ x₀ mod 2^k

for k = 31, but also for smaller k. We could set k = 8 and prove that there are only 64 values, or set k = 4 and prove that there are only four final hex digits.