Middle-square method

Middle-square method
One iteration of the middle-square method, showing a six digit seed, which is then squared, and the resulting value has its middle six digits as the output value (and also as the next seed for the sequence).

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.[1]

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 zeroes 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."[1] Nicholas Metropolis reported sequences of 750,000 digits before "destruction" by means of using 38-bit numbers with the "middle-square" method.[2]

References

  1. ^ a b The 1949 papers were not reprinted until 1951. John von Neumann, “Various techniques used in connection with random digits,” in A.S. Householder, G.E. Forsythe, and H.H. Germond, eds., Monte Carlo Method, National Bureau of Standards Applied Mathematics Series, vol. 12 (Washington, D.C.: U.S. Government Printing Office, 1951): pp. 36-38.
  2. ^ Donald E. Knuth, The art of computer programming, Vol. 2, Seminumerical algorithms, 2nd edn. (Reading, Mass.: Addison-Wesley, 1981), ch. 3, section 3.1.

See also



Wikimedia Foundation. 2010.

Игры ⚽ Поможем сделать НИР

Look at other dictionaries:

  • Mid-square-method — Die Mittquadratmethode (auch Mid Square Methode oder mittlere Quadratmethode genannt; aus dem englischen middle square method oder mid square method) wurde 1946 von John von Neumann als einer der ersten Zufallszahlengeneratoren vorgestellt. Erst… …   Deutsch Wikipedia

  • Mid-square method — Die Mittquadratmethode (auch Mid Square Methode oder mittlere Quadratmethode genannt; aus dem englischen middle square method oder mid square method) wurde 1946 von John von Neumann als einer der ersten Zufallszahlengeneratoren vorgestellt. Erst… …   Deutsch Wikipedia

  • Mid square method — Die Mittquadratmethode (auch Mid Square Methode oder mittlere Quadratmethode genannt; aus dem englischen middle square method oder mid square method) wurde 1946 von John von Neumann als einer der ersten Zufallszahlengeneratoren vorgestellt. Erst… …   Deutsch Wikipedia

  • Monte Carlo method — Not to be confused with Monte Carlo algorithm. Computational physics …   Wikipedia

  • Mid-Square-Methode — Die Mittquadratmethode (auch Mid Square Methode oder mittlere Quadratmethode genannt; aus dem englischen middle square method oder mid square method) wurde 1946 von John von Neumann als einer der ersten Zufallszahlengeneratoren vorgestellt. Erst… …   Deutsch Wikipedia

  • Mid-square methode — Die Mittquadratmethode (auch Mid Square Methode oder mittlere Quadratmethode genannt; aus dem englischen middle square method oder mid square method) wurde 1946 von John von Neumann als einer der ersten Zufallszahlengeneratoren vorgestellt. Erst… …   Deutsch Wikipedia

  • Mid square methode — Die Mittquadratmethode (auch Mid Square Methode oder mittlere Quadratmethode genannt; aus dem englischen middle square method oder mid square method) wurde 1946 von John von Neumann als einer der ersten Zufallszahlengeneratoren vorgestellt. Erst… …   Deutsch Wikipedia

  • Square One (puzzle) — This article is about the puzzle. For the popular phrase, see Back to square one. The Square One, also known as Back to Square One and Cube 21, is a puzzle similar to the Rubik s Cube. Its distinguishing feature among the numerous Rubik s Cube… …   Wikipedia

  • Square root of 5 — The square root of 5 is the positive real number that, when multiplied by itself, gives the prime number 5. This number appears in the formula for the golden ratio. It can be denoted in surd form as::sqrt{5}.It is an irrational algebraic number.… …   Wikipedia

  • Magic square — In recreational mathematics, a magic square of order n is an arrangement of n2 numbers, usually distinct integers, in a square, such that the n numbers in all rows, all columns, and both diagonals sum to the same constant.[1] A normal magic… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”