Middle-square method: Difference between revisions

Revision as of 01:30, 23 May 2025

Latest revision as of 00:52, 8 August 2025

(3 intermediate revisions by 2 users not shown)

Line 3:

[[Image:Middle_square_method_2_digits.svg|right|250px|thumb|[[Directed graph]] of all 100 2-digit pseudorandom numbers obtained using the middle-square method with ''n'' = 2.]]

In [[mathematics]] and [[computer science]], the '''middle-square method''' is a method of generating [[pseudorandom number]]s. In practice it is a highly flawed method for many practical purposes, since its [[Pseudorandom number generator#Periodicity|period]] is usually very short and it has some severe weaknesses; repeated enough times, the middle-square method will either begin repeatedly generating the same number or cycle to a previous number in the sequence and loop indefinitely.

== History ==

Line 11:

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

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–14 }}</ref><ref>{{cite arXiv | last=Widynski | first=Bernard | eprint=1704.00358 | title=Middle-Square Weyl Sequence RNG | date=April 2017| class=cs.CR }}</ref>

Line 25:

Here, the algorithm is rendered in [[Python 3|Python 3.12]].

<syntaxhighlight lang="python" line="1">

numberseed_number = int(input("Please enter a four-digit number:\n[####] "))

number = seed_number

already_seen = set()

counter = 0

Line 36 ⟶ 37:

print(f"#{counter}: {number}")

print(f"We began with {numberseed_number} and"

f" have repeated ourselves after {counter} steps"

f" with {number}.")