The Middle Square
Von Neumann described this at the Monte Carlo symposium in Los Angeles at the end of June 1949, and it is where the line about being in a state of sin comes from. Square a four-digit number, keep the middle four digits of the eight, and do it again. What makes it worth a page is that the whole state space is ten thousand values, which is small enough to count completely rather than sample: every seed there is falls into one of eight cycles, and the median seed hands you forty-five numbers before it starts repeating itself.
Square it, keep the middle, and watch where that ends
1 One seed, squared, and the middle four digits
Type any four-digit seed. Everything else on this page follows it.
2 The run, and the step where a value comes back
The same step, applied to its own output until a value turns up twice. Once one does, the sequence is trapped: the step depends on nothing but the current value, so the same value must always be followed by the same one.
3 Which of the seventeen it drained into, and who else lands there
There are only seventeen values a sequence can end on. Every one of the ten thousand seeds drains into one of them, and knowing which one tells you the whole rest of the sequence.
4 The whole space enumerated: eight cycles, none longer than four
Those seventeen values make eight cycles, five of which are single values that map to themselves. This table was counted in this browser a moment ago by running every one of the ten thousand seeds to its end. Nothing here is sampled or estimated.
| cycle | length | seeds | share |
|---|
These ran in this browser when the page loaded. Each claim, whether it held, and the number behind it. The expected values are Brian Hayes's, who enumerated the same space in 2022 and published his counts, so a disagreement here is a disagreement with somebody outside this site.
| claim | held | measured |
|---|---|---|
| Taking the middle four characters and dividing by a hundred are the same step | yes | agreed on all 10,000 inputs |
| Every seed ends in one of eight cycles | yes | counted 8, Hayes counted 8 |
| Five of those eight are fixed points, and the other three have length four | yes | 0, 100, 2500, 3792, 7600 are fixed; the loops are 6100-2100-4100-8100, 9600-1600-5600-3600 and 2916-5030-3009-540 |
| No cycle is longer than four, out of a space of ten thousand | yes | longest cycle 4 in 10,000 values |
| The space divides into seventeen watersheds | yes | counted 17, Hayes counted 17 |
| The longest run any seed produces is 111 values, from 6239 | yes | measured 111 from seed 6239 |
| The median seed produces 45 values before one comes back | yes | measured 45 of a possible 10,000 |
| 1,968 seeds reach zero and stop there | yes | measured 1968 (19.7% of all seeds) |
| 3,116 seeds arrive at 6100, and 3792 has no tributaries at all | yes | 6100 takes 3116; 3792 is reached by 0 seeds other than itself |
| The smallest of the three loops drains 86 values, and no path through them is longer than 15 | yes | 86 values, longest path 15, median 10 |
What is real here, and what is not
The words everybody quotes are Forsythe's, not von Neumann's
The source is a three-page item in the 1951 proceedings whose byline reads By John von Neumann
and immediately under it Summary written by George E. Forsythe
. Von Neumann gave the talk; Forsythe wrote down what he said. So the sentence about being in a state of sin, which is quoted on every page about this method including this one, is a summary of a spoken remark rather than something von Neumann wrote. That is worth knowing before repeating it as his prose.
Von Neumann's own description is ten digits wide, not four
The summary describes obtaining a value as the middle ten digits
of the square of a ten-digit number. The quotation stops there because the scan does not spell the next word: the OCR of this page renders square
as s<I,uare, and tidying that silently is how a quotation stops matching the document it claims to come from. Four digits is the teaching size, small enough that the entire state space fits in a browser and can be counted rather than sampled, and it is the size Brian Hayes used for the same reason. Nothing here should be read as von Neumann proposing a four-digit generator. The failure is the same shape at both widths and the numbers on this page are the four-digit ones.
The numbers are counted, not sampled, and checked against somebody else
Every quantity on this page comes from running all ten thousand seeds to their end when the page loaded. There is no sampling and no random seeding anywhere in it. The expected values in the checks are the ones Brian Hayes published in 2022 after enumerating the same space independently, which is the point of using them: they are a witness this site does not control. Eight quantities agree, including the longest run of 111 from seed 6239, the median of 45, the 1,968 seeds that reach zero and the 86-value component around the smallest loop.
The step is computed two ways on purpose
Slicing the middle four characters out of the zero-padded square and dividing the square by a hundred are different routes to the same value, sharing no code. The page runs both on all ten thousand inputs when it loads and says whether they agreed. A page whose entire argument is an arithmetical census should not be trusted to do the arithmetic one way.
A cycle of length one is still counted as a cycle
Five of the eight are fixed points: 0, 100, 2500, 3792 and 7600 each map to themselves. Hayes writes the same set as three cycles of length four plus five fixed points, which is the same eight things described differently. Counting them together is what makes the sentence about eight cycles true, and it is said here rather than left for a reader to reconcile.
The date is the talk, and two other dates have a claim on it
The chronology takes 1949, the Monte Carlo symposium held in Los Angeles from 29 June to 1 July. The write-up appeared in 1951. There is a third date, the first use on ENIAC, and the sources here do not agree on it: Brian Hayes puts the method at circa 1947, while planning the first computer simulations of nuclear fission
and the first Monte Carlo run in the spring of 1948, while this studio's own research note had written 1946. Nothing primary read for this page settles it, so the page does not pick one, and the year on the chronology is the talk rather than the first use. That is the earliest of the three that has a date anybody can read. The reprint consulted here carries a running head reading Appl. Math. Series 3
, which does not match the volume: the proceedings are Applied Mathematics Series 12, and the citation follows the volume rather than the header.
This is not a plot of randomness
Nothing here tests whether the numbers look random, because that is not the interesting failure. The middle square fails long before any statistical test is needed: it runs out. A generator whose median supply is forty-five values from a space of ten thousand has already lost, and the page argues from the census rather than from a histogram.
No sound
Nothing here has a duration. A sequence has a length, and a length is read.
Sources
- John von Neumann, Various Techniques Used in Connection With Random Digits, summary written by George E. Forsythe, in Monte Carlo Method, National Bureau of Standards Applied Mathematics Series 12, 1951, pages 36 to 38, reprinted in the Collected Works. Read for this page: the byline, the sentence about a state of sin, and the description of taking the middle digits of the square of a ten-digit number.
- Brian Hayes, The Middle of the Square, bit-player, 8 August 2022. The independent enumeration of the same state space that the checks on this page are measured against: the cycles and fixed points, the seventeen watersheds, the longest and median run lengths, and the component around the smallest cycle.
- Logical Art, the studio this belongs to.