# A Truly Horrible Random Number Generator

### When you were learning to code, you probably created a simply random number generator. In this post, a PhD in mathematics looks at the worst one he's encountered.

Join the DZone community and get the full member experience.

Join For FreeI 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*_{0} and generates subsequent values via

*x*_{n+1} = 65539 *x*_{n} mod 2^{31}

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^{n} *x*_{0} 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.

Published at DZone with permission of John Cook, DZone MVB. See the original article here.

Opinions expressed by DZone contributors are their own.

Comments