Middle-square method
Encyclopedia
In mathematics
, the middle-square method is a method of generating pseudorandom numbers. In practice it is not a good method, since its period is usually very short and it has some crippling weaknesses. The method originated with John von Neumann
, and was notably described at a conference in 1949.
To generate a sequence of ten-digit pseudorandom numbers, a 4-digit starting value is created and squared, producing an 8-digit number (if the result is less than 8 digits, leading zero
es are added to compensate). The middle 4 digits of the result would be the next number in the sequence, and returned as the result. This process is then repeated to generate more numbers.
For a generator of n-digit numbers, the period can be no longer than 8n. If the middle 4 digits are all zeroes, the generator then outputs zeroes forever. If the first half of a number in the sequence is zeroes, the subsequent numbers will be decreasing to zero. While these runs of zero are easy to detect, they occur too frequently for this method to be of practical use. The middle-squared method can also get stuck on a number other than zero. For n=4, this occurs with the values 0100, 2500, 3792, and 7600. Other seed values form very short repeating cycles, e.g., 0540-2916-5030-3009. These phenomena are even more obvious when n=2, as none of the 100 possible seeds generates more than 14 iterations without reverting to 0, 10, 60, or a 24-57 loop.
In the 1949 talk, Von Neumann famously quipped that, "Any one who considers arithmetical methods of producing random digits is, of course, in a state of sin
." What he meant, he elaborated, was that there were no true "random numbers," just means to produce them, and "a strict arithmetic procedure," like the one described above, "is not such a method." Nevertheless he found these kinds of methods much quicker (hundreds of times faster) than reading "truly" random numbers off punch cards, which had practical importance for his ENIAC
work. He found the "destruction" of middle-square sequences to be a factor in their favor, because it could be easily detected: "one always fears the appearance of undetected short cycles." Nicholas Metropolis
reported sequences of 750,000 digits before "destruction" by means of using 38-bit numbers with the "middle-square" method.
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, the middle-square method is a method of generating pseudorandom numbers. In practice it is not a good method, since its period is usually very short and it has some crippling weaknesses. The method originated with John von Neumann
John von Neumann
John von Neumann was a Hungarian-American mathematician and polymath who made major contributions to a vast number of fields, including set theory, functional analysis, quantum mechanics, ergodic theory, geometry, fluid dynamics, economics and game theory, computer science, numerical analysis,...
, and was notably described at a conference in 1949.
To generate a sequence of ten-digit pseudorandom numbers, a 4-digit starting value is created and squared, producing an 8-digit number (if the result is less than 8 digits, leading zero
Leading zero
A leading zero is any 0 digits, that lead a number string in a positional notation. For example, James Bond's famous identifier, 007, has two leading zeros. Leading zeros occupy most significant digits, which could be left blank or omitted for the same numeric value...
es are added to compensate). The middle 4 digits of the result would be the next number in the sequence, and returned as the result. This process is then repeated to generate more numbers.
For a generator of n-digit numbers, the period can be no longer than 8n. If the middle 4 digits are all zeroes, the generator then outputs zeroes forever. If the first half of a number in the sequence is zeroes, the subsequent numbers will be decreasing to zero. While these runs of zero are easy to detect, they occur too frequently for this method to be of practical use. The middle-squared method can also get stuck on a number other than zero. For n=4, this occurs with the values 0100, 2500, 3792, and 7600. Other seed values form very short repeating cycles, e.g., 0540-2916-5030-3009. These phenomena are even more obvious when n=2, as none of the 100 possible seeds generates more than 14 iterations without reverting to 0, 10, 60, or a 24-57 loop.
In the 1949 talk, Von Neumann famously quipped that, "Any one who considers arithmetical methods of producing random digits is, of course, in a state of sin
Sin
In religion, sin is the violation or deviation of an eternal divine law or standard. The term sin may also refer to the state of having committed such a violation. Christians believe the moral code of conduct is decreed by God In religion, sin (also called peccancy) is the violation or deviation...
." What he meant, he elaborated, was that there were no true "random numbers," just means to produce them, and "a strict arithmetic procedure," like the one described above, "is not such a method." Nevertheless he found these kinds of methods much quicker (hundreds of times faster) than reading "truly" random numbers off punch cards, which had practical importance for his ENIAC
ENIAC
ENIAC was the first general-purpose electronic computer. It was a Turing-complete digital computer capable of being reprogrammed to solve a full range of computing problems....
work. He found the "destruction" of middle-square sequences to be a factor in their favor, because it could be easily detected: "one always fears the appearance of undetected short cycles." Nicholas Metropolis
Nicholas Metropolis
Nicholas Constantine Metropolis was a Greek American physicist.-Work:Metropolis received his B.Sc. and Ph.D. degrees in physics at the University of Chicago...
reported sequences of 750,000 digits before "destruction" by means of using 38-bit numbers with the "middle-square" method.
See also
- Linear congruential generatorLinear congruential generatorA Linear Congruential Generator represents one of the oldest and best-known pseudorandom number generator algorithms. The theory behind them is easy to understand, and they are easily implemented and fast....
- Blum Blum Shub