Middle-square method: Difference between revisions

Revision as of 14:56, 21 June 2010

Revision as of 23:08, 16 August 2010

Line 1:

{{Unreferenced|auto=yes|date=December 2009}}

[[Image:Middle-square method.svg|right|250px|thumb|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 number]]s. In practice it is not a good method, since its period is usually very short and it has some crippling weaknesses. The method was firstnotably suggested by [[Johnjohn Vonvon Neumann]] at a conference in 1946{{Citation1949.<ref needed|datename=June"vonneumann">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. 2010}}36-38.</ref>

To generate a sequence of ten-digit pseudorandom numbers, a 4-digit starting value is created and squared. 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.

Line 11 ⟶ 10:

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.

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 number off of [[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."<ref name="vonneumann"></ref> [[Nicholas Metropolis]] reported sequences of 750,000 digits before "destruction" by means of using 38-bit numbers with the "middle-square" method.<ref>Donald E. Knuth, ''The art of computer programming, Vol. 2, Seminumerical algorithms,'' 2nd edn. (Reading, Mass.: Addison-Wesley, 1981), ch. 3, section 3.1.</ref>

Von Neumann was aware of these problems, but for his purposes the middle-square method was quick (important for use on the [[ENIAC]]), and its errors were easy to detect (when it failed, it generally failed spectacularly).

==References==

<references/>

==See also==