To install click the Add extension button. That's it.

The source code for the WIKI 2 extension is being checked by specialists of the Mozilla Foundation, Google, and Apple. You could also do it yourself at any point in time.

4,5
Kelly Slayton
Congratulations on this excellent venture… what a great idea!
Alexander Grigorievskiy
I use WIKI 2 every day and almost forgot how the original Wikipedia looks like.
Live Statistics
English Articles
Improved in 24 Hours
Added in 24 Hours
Languages
Recent
Show all languages
What we do. Every page goes through several hundred of perfecting techniques; in live mode. Quite the same Wikipedia. Just better.
.
Leo
Newton
Brights
Milds

Middle-square method

From Wikipedia, the free encyclopedia

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).
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).
Directed graph of all 100 2-digit pseudorandom numbers obtained using the middle-square method with n = 2.
Directed graph of all 100 2-digit pseudorandom numbers obtained using the middle-square method with n = 2.

In mathematics, the middle-square method is a method of generating pseudorandom numbers. In practice it is not a good method, since its 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.

YouTube Encyclopedic

  • 1/3
    Views:
    2 880
    191 239
    565 969
  • ✪ hashing methods | digit extraction & mid square| part 3 | by bhanu priya
  • ✪ Completing the Square Method in Quadratic Equation (Hindi) | NCERT 10th Class Maths
  • ✪ Factoring Trinomials The Easy Fast Way

Transcription

Contents

History

In Mathematics

The method was invented by John von Neumann, and was described at a conference in 1949.[1]

In the 1949 talk, Von Neumann 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 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."[1] Nicholas Metropolis reported sequences of 750,000 digits before "destruction" by means of using 38-bit numbers with the "middle-square" method.[2]

First Invention Theory

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.[3] 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 2n-digit number. If the result has fewer than 2n digits, leading zeroes 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-- 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: 5402 = 291600). If there were to be a middle three digit that would leave 6 - 3 = 3 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 (eg: 540 → 0540).

For a generator of n-digit numbers, the period can be no longer than 8n. 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 = 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, 50, 60, or a 24 ↔ 57 loop.

Example Implementation

Here, the algorithm is rendered in Python 3.

seed_number = int(input("Please enter a four digit number:\n[####] "))
number = seed_number
already_seen = set()
counter = 0

while number not in already_seen:
    counter += 1
    already_seen.add(number)
    number = int(str(number * number).zfill(8)[2:6]) # zfill adds padding of zeroes
    print(f"#{counter}: {number}")

print(f"We began with {seed_number}, and"
      f" have repeated ourselves after {counter} steps"
      f" with {number}.")

Middle Square Weyl Sequence PRNG

The defects associated with the original middle-square generator can be rectified by running the middle square with a Weyl sequence[4][5]. The Weyl sequence prevents convergence to zero. The Weyl sequence also prevents the repeating cycle problem described above. A C implementation is shown below.

#include <stdint.h>

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

inline static uint32_t msws() {

   x *= x; 
   x += (w += s); 
   return x = (x>>32) | (x<<32);

}

The Weyl sequence (w += s) is added to the square of x. The middle is extracted by shifting right 32 bits. This generator passes BigCrush[6][7]. and PractRand[8]. This may be the world's fastest PRNG for producing 32-bit floating-point numbers[4]. A free software package is available here[5].

References

  1. ^ a b 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.
  2. ^ Donald E. Knuth, The art of computer programming, Vol. 2, Seminumerical algorithms, 2nd edn. (Reading, Mass.: Addison-Wesley, 1981), ch. 3, section 3.1.
  3. ^ Ivar Ekeland (15 June 1996). The Broken Dice, and Other Mathematical Tales of Chance. University of Chicago Press. ISBN 978-0-226-19992-4.
  4. ^ a b Widynski, Bernard (April 2017). "Middle Square Weyl Sequence RNG". arXiv:1704.00358v3.
  5. ^ a b Middle Square Weyl Sequence RNG website.
  6. ^ Pierre L’Ecuyer & Richard Simard (2007), "TestU01: A Software Library in ANSI C for Empirical Testing of Random Number Generators", ACM Transactions on Mathematical Software, 33: 22.
  7. ^ The TestU01 web site.
  8. ^ Chris Doty-Humphrey (2018), "Practically Random: C++ library of statistical tests for RNGs." version 0.94.

See also

This page was last edited on 12 May 2019, at 16:42
Basis of this page is in Wikipedia. Text is available under the CC BY-SA 3.0 Unported License. Non-text media are available under their specified licenses. Wikipedia® is a registered trademark of the Wikimedia Foundation, Inc. WIKI 2 is an independent company and has no affiliation with Wikimedia Foundation.