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 = 65539 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.) 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
xn = 65539n x0 mod 2k
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.
I think it would be worth pointing out that the images start with a black background and more frequent values are lighter. As the rest of the site is black on white, it took me a while to figure out how you got 64 out of 256 in the first one :)
I remember back when LCGs were thought of as “the best RNG for the least work”. That is, if you were starved for CPU cycles and/or memory, an LCG was the way to go. But not doing enough work setting up your LCG makes for a terrible RNG.
Ref: https://en.wikipedia.org/wiki/Linear_congruential_generator (be sure to check the last entry in the LCG list…)
Here’s a worse one:
x_{n+1} = 0*x_{n} + 9
:-)
By taking the n least significant bits, not only is it 2^(n-2) unique values, 2^(n-2) is the rng period.