Middle-square method: Difference between revisions

Revision as of 23:42, 31 March 2013

Revision as of 04:25, 2 April 2013

Line 5:

The method was first described in a manuscript by a Franciscan friar (known only as Brother Edvin) sometime between 1240 and 1250.<ref name="Ekeland1996">{{cite book|author=Ivar Ekeland|title=The Broken Dice, and Other Mathematical Tales of Chance|accessdate=27 January 2013|date=15 June 1996|publisher=University of Chicago Press|isbn=978-0-226-19992-4}}</ref> It was reinvented by [[John von Neumann]], and was notably described at a conference in 1949.<ref name="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. 36-38.</ref>

To generate a sequence of ten-digit{{clarify|reason=how 10-digit number is produced from 4- and 8-digit numbers?}} 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 8^''n''. 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.".<ref name="vonneumann"/> [[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>

==Example Source Code{{OR}}==

<source lang="c">

for (int i = 0; i < samplesToProduce; i++i)

{

for( i = 0; i < samplesToProduce; i++)

{

//select the middle six digits for the next seed

newseed = (x / 1000) % 1000000;

Line 23 ⟶ 21:

//to the algorithm would be reseeding with the time as seen below.

/*

if (newseed < threshHold){

newseed = time(NULL);

}

*/

x = newseed * newseed;

storageArray[i] = x;

}

</source>