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 viaxn+1 = 65539 xn mod 231I 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 thatxn = 65539n x0 mod 2kfor 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.
Related postsRNG seed mistakesChaCha RNGTesting RNGs with PractRand.