Von Neumann proposed the middle square method of generating pseudo-random numbers in 1949, in a paper published a bit later. The method is simple: you take a seed, say 4 digits long, you square it, and extract the middle 4 digits, which become the next seed. For example:
While it seems random enough, is it?
A good pseudo-random generator should not depend much on the seed. It should also have a maximally long period, that is, visit every number in its range before it starts repeating itself. The transition graph would be just one big cycle.
well, the middle square generator does both very badly:
- Depending on the seed, you may get very quickly into a cycle. For example, using a 2 digit seed, you get . Another example would be , or .
- The squaring operator isn’t very good at covering its range. We may think it’s a good operation because if you feed it different numbers you’ll get results, but you don’t. As we extract only the middle digits, we find that abound only 60% of the different values are actually reached (that seems to be true regardless of how many digits we use).
- The path from a seed to a cycle can be long, but cycles, when they occur, are very short.
Let’s have a look at an example were we input 2 digits, get 4 digits, then extract 2. Using Graphviz, we get the following graph:
We see that, indeed, 15, 35, 65, and 85 all yield 22, which isn’t very efficient. What about more digits? Say, 3? We get:
We still see the same general effects, except that now there are cycles of length 4.
While it is not a very good pseudo-random number generator, it is still sometimes proposed as a hash function. But since 15, 35, 65, and 85 all yield 22, it would indicate it is as good a hash function as it is a pseudorandom generator.