The Middle Square Method (Generating Random Sequences VIII)

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 50\to{}2500\to{}50. Another example would be 60, or 24\to{}576\to{}57\to{}3249\to{}24.
  • The squaring operator isn’t very good at covering its range. We may think it’s a good operation because if you feed it n different numbers you’ll get n^2 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:

(Click to embiggen)

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:

(Click to inflatize)

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.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: