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:

4373\to{}19123129\to{}1231.

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.

6 Responses to The Middle Square Method (Generating Random Sequences VIII)

  1. […] of the first simple methods of generating pseudo-random numbers, the middle square method, was invented by the mathematician John von Neumann in 1949. You take a numeric seed with an even […]

  2. […] of the first simple methods of generating pseudo-random numbers, the middle square method, was invented by the mathematician John von Neumann in 1949. You take a numeric seed with an even […]

  3. […] 1st simple methods of generating pseudo-random №s, the middle □ method, was invented by the mathematician john von neumann in 1949. you take a numeric seed with an even […]

  4. […] of the first simple methods of generating pseudo-random numbers, the middle square method, was invented by the mathematician John von Neumann in 1949. You take a numeric seed with an even […]

  5. […] of the first simple methods of generating pseudo-random numbers, the middle square method, was invented by the mathematician John von Neumann in 1949. You take a numeric seed with an even […]

  6. […] 1st simple methods of generating pseudo-random №s, the middle □ method, was invented by the mathematician john von neumann in 1949. you take a numeric seed with an even […]

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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: