Middle-square method: Difference between revisions

Revision as of 12:17, 21 October 2021

Revision as of 12:21, 21 October 2021

Line 6:

== History ==

===In mathematics===

The method was invented by [[John von Neumann]], and was 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 digitsdigits”,” in A.&nbsp;S. Householder, G.&nbsp;E. Forsythe, and H.&nbsp;H. Germond, eds., ''Monte Carlo Method, National Bureau of Standards Applied Mathematics Series'', vol. &nbsp;12 (Washington, D.C.: U.S. Government Printing Office, 1951): pp. &nbsp;36–38.</ref>

In the 1949 talk, Von Neumann quipped that, "Anyone 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 middle-square method, "is not such a method.". Nevertheless, he found these methods 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. &nbsp;2, Seminumerical algorithms,'', 2nd edn. (Reading, Mass.: Addison-Wesley, 1981), ch. &nbsp;3, section &nbsp;3.1.</ref>

The book ''The Broken Dice'' by [[Ivar Ekeland]] gives an extended account of how the method was invented 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 |date=15 June 1996 |publisher=University of Chicago Press |isbn=978-0-226-19992-4}}</ref> Supposedly, the manuscript is now lost, but [[Jorge Luis Borges]] sent Ekeland a copy that he made at the Vatican Library.

The book ''The Broken Dice'' by [[Ivar Ekeland]] gives an extended account of how the

method was invented 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|date=15 June 1996|publisher=University of Chicago Press|isbn=978-0-226-19992-4}}</ref> Supposedly, the manuscript is now lost, but [[Jorge Luis Borges]] sent Ekeland a copy that he made at the Vatican Library.

Modifying the middle -square algorithm with a [[Weyl sequence]] improves period and randomness. <ref>{{cite book | title = Random Numbers and Computers | last = Kneusel | first = Ron | publisher = Springer | year = 2018 | edition = 1 | pages = 13-1413–14 }}</ref> <ref>{{cite arXiv | last=Widynski | first=Bernard | eprint=1704.00358 | title=Middle Square Weyl Sequence RNG | date=April 2017}}</ref>

== The method ==