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 . 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:

(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.

This entry was posted on Tuesday, November 21st, 2017 at 11:27 am and is filed under algorithms, Mathematics. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.

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

[…] 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 […]

[…] 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 […]

[…] 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 […]

[…] 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 […]

[…] 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 […]

[…] 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 […]

RT @SebAaltonen: Let's talk about 4x4 matrices with implicit (0,0,0,1) last column. We often call these 4x3 matrices (or 3x4 matrices depen… 12 hours ago

RT @DothTheDoth: Dracula had it right, sleep all day, live alone in a castle & explode into a thousand bats to get out of social situations. 12 hours ago

[…] 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 […]

[…] 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 […]

[…] 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 […]

[…] 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 […]

[…] 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 […]