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 1960’s, 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 x0 and generates subsequent values via
xn+1 = 645539 xn mod 231
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.
You can see the pattern from printing 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.