Middle-square method: Difference between revisions

Revision as of 15:44, 26 April 2021

Latest revision as of 00:52, 8 August 2025

(48 intermediate revisions by 25 users not shown)

Line 1:

{{Short description|Pseudorandom number generator}}

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

[[Image:Middle_square_method_2_digitsMiddle-square method.svg|right|250px|thumb|[[DirectedOne graph]]iteration of allthe middle-square method, showing 100a 26-digit pseudorandomseed, numberswhich obtainedis usingthen squared, and the resulting value has its middle-square method6 digits withas ''n''the =output value (and also as the next seed for the 2sequence).]]

[[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 not a goodhighly 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 ==

===In mathematics===

The method was invented by [[John von Neumann]], and was described by him 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]].

===First invention theory===

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

InModifying the bookmiddle-square "Randomalgorithm Numberswith a [[Weyl sequence]] improves period and Computers”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 KneuselarXiv states| thelast=Widynski following:| first=Bernard | eprint=1704.00358 | title=Middle-Square Weyl Sequence RNG | date=April 2017| class=cs.CR }}</ref>

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 method ==

To generate a sequence of ''n''-digit pseudorandom numbers, an ''n''-digit starting value is created and squared, producing a 2n2''n''-digit number. If the result has fewer than 2n2''n'' digits, [[leading zero]]es are added to compensate. The middle ''n'' 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.

The value of ''n'' must be even in order for the method to work--{{snd}} if the value of ''n'' is odd, then there will not necessarily be a uniquely defined '"middle ''n''-digits'" to select from. Consider the following: If a 3-digit number is squared, it can yield a 6 -digit number (eg:e.g. 540^''2'' = 291600). If there were to be a middle three digit3&nbsp;digits, that would leave 6 − 3 = 3 &nbsp;digits to be distributed to the left and right of the middle. It is impossible to evenly distribute these digits equally on both sides of the middle number, and therefore there are no '"middle digits".' It is acceptable to pad the seeds with zeros to the left in order to create an even valued ''n''-digit number (eg:e.g. 540 &nbsp;→ &nbsp;0540).

For a generator of ''n''-digit numbers, the period can be no longer than 8^''n''. If the middle ''n'' 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'' &nbsp;= &nbsp;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'' &nbsp;= &nbsp;2, as none of the 100 possible seeds generates more than 14 iterations without reverting to 0, 10, 50, 60, or a 24 ↔ 57 loop.

=== Example implementation ===

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

<syntaxhighlight lang="python">

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

number = seed_number

already_seen = set()

Line 35 ⟶ 37:

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

print(f"We began with {seed_number}, and"

f" have repeated ourselves after {counter} steps"

f" with {number}.")

</syntaxhighlight>

==RecentSee developmentsalso==

* [[Linear congruential generator]]

* [[Blum Blum Shub]]

In the book "Random Numbers and Computers”<ref>{{cite book | title = Random Numbers and Computers | last = Kneusel | first = Ron | publisher = Springer | year = 2018 | edition = 1 | pages = 13-14 }}</ref>, Kneusel states the following:

* [[Hash function#Mid-squares | middle-square hash function ]]

“Interestingly, recently (as of 2017) the middle square method has resurfaced. In "Middle Square Weyl Sequence RNG"<ref name="mswsrng">{{cite arXiv | last=Widynski | first=Bernard | eprint=1704.00358v5 | title=Middle Square Weyl Sequence RNG | date=April 2017}}</ref> Widynski proposes a straightforward modification of the middle square algorithm which results in a very fast generator with a respectable period, excellent results in randomness tests, and easy application in parallel”.

A [[Weyl sequence]] is used to run the middle square. The [[Weyl sequence]] provides uniformity and a known minimum period; the middle square provides randomization. The combined generator passes very stringent tests of randomness including the BigCrush<ref name="TestU01">L’Ecuyer, Pierre; Simard, Richard (2007), [http://simul.iro.umontreal.ca/testu01/tu01.html TestU01 BigCrush].</ref> and PractRand<ref name = "PractRand">Doty-Humphrey, Chris (2018), "[http://pracrand.sourceforge.net Practically Random: C++ library of statistical tests for RNGs.]" version 0.94.</ref> tests. Many commonly used RNGs do not pass these tests.

A [[C_(programming_language)|C]] language implementation is shown below.

<syntaxhighlight lang="c">

#include <stdint.h>

uint64_t x = 0, w = 0, s = 0xb5ad4eceda1ce2a9;

inline static uint32_t msws() {

x *= x; /* Compute square of x */

x += (w += s); /* Add Weyl sequence */

return x = (x>>32) | (x<<32); /* Rotate and return 32 bits from middle */

}

</syntaxhighlight>

A [[Counter-based random number generator (CBRNG) | counter-based]] version was published in 2020, “Squares: A Fast Counter-Based RNG”<ref>{{cite arXiv| last=Widynski | first=Bernard | arxiv=2004.06278v3 | title=Squares: A Fast Counter-Based RNG | date=April 2020}}</ref>. [[Counter-based random number generator (CBRNG) | Counter-based]] RNGs are well suited to parallel processing<ref>{{Cite conference|title = Parallel random numbers: as easy as 1, 2, 3|last = Salmon|first = John|date = 2011|book-title = Proceedings of 2011 International Conference for High Performance Computing, Networking, Storage and Analysis, Article No. 16|doi = 10.1145/2063384.2063405|last2 = Moraes|first2 = Mark|last3 = Dror|first3 = Ron|last4 = Shaw|first4 = David}}</ref>. Four rounds of squaring are applied to a counter to produce a random output. Squares may be the fastest RNG in this category. The squares generator is shown below.

<syntaxhighlight lang="c">

#include <stdint.h>

inline static uint32_t squares(uint64_t ctr, uint64_t key) {

uint64_t x, y, z;

y = x = ctr * key; z = y + key; /* Compute ctr*key and (ctr+1)*key */

x = x*x + y; x = (x>>32) | (x<<32); /* Round 1 */

x = x*x + z; x = (x>>32) | (x<<32); /* Round 2 */

x = x*x + y; x = (x>>32) | (x<<32); /* Round 3 */

return (x*x + z) >> 32; /* Round 4 */

}

</syntaxhighlight>

==References==

<references/>

==See also==

* [[Linear congruential generator]]

* [[Blum Blum Shub]]

{{DEFAULTSORT:Middle-Square Method}}

Line 100 ⟶ 54:

[[Category:Articles with example C code]]

[[Category:Articles with example Python (programming language) code]]

[[Category:John von Neumann]]