Square it and keep the middle

In the late 1940s John von Neumann needed random numbers for the first computer simulations of neutron diffusion, and he needed them faster than a table could be read in. His proposal was the simplest arithmetic rule anyone could think of. Take a number with, say, four digits. Square it, which gives eight digits, padding with zeros at the front if needed. Keep the middle four. That is the next number. Repeat.

Starting from $6239$: its square is $38925121$, whose middle four digits are $9251$; that squared is $85581001$, giving $5810$; then $7561$, $1687$, and on. The digits look patternless, and for a while they are. But there are only ten thousand four-digit numbers, so the sequence must eventually return to a number it has already produced, and from then on it repeats the same loop for ever. The question that decides whether the rule is any use is how soon that happens.

Von Neumann knew the answer was “too soon, sometimes”, and said so with a sentence that has been quoted ever since: anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin. He used the method anyway, on the grounds that its failures were easy to detect. With a computer it is now possible to do what he could not: follow every seed to the end.

What the rule was for #

The setting matters for judging the rule fairly. In 1946 Stanisław Ulam and von Neumann had worked out that the behaviour of neutrons in a fissile core could be estimated by following many imaginary neutrons through a sequence of random events — scattering, absorption, fission — and averaging. The method needed random numbers by the hundred thousand, and the machine that would run it, the ENIAC, had almost no memory: a table of random digits could not be stored, and reading one from punched cards was slower than the arithmetic it fed. The RAND Corporation’s book of a million random digits, produced from an electronic noise source, did not appear until 1955.

So the requirement was a rule the machine could compute from its own last output, in a few instructions, using nothing but the arithmetic it already had. Squaring is one multiplication. Extracting the middle digits is a shift and a mask. Von Neumann presented the method at a symposium on Monte Carlo methods in 1949, and the published version of 1951 is where the sentence about sin appears, in the same paragraph that recommends the method: he argued that a rule which fails by collapsing into a short loop fails visibly, and a calculation can be watched for it, whereas a subtler rule might fail invisibly. The census above is the systematic version of that watching.

Why the middle and not the ends #

The choice of the middle digits is not arbitrary, and the reason also explains the traps.

The last digits of a square depend only on the last digits of the number. The last two digits of $x^2$ are fixed by the last two digits of $x$, because the rest of $x$ contributes multiples of a hundred. Keeping the end of the square would therefore make the rule a map on a hundred values in disguise, with all of the shortness that implies. The first digits of a square, on the other hand, depend mostly on the first digits of the number, and hardly at all on the last. Keeping the front would ignore half the input.

The middle digits are where both halves of the input meet: they collect the cross term $2ab$ when the number is written as $a$ hundreds plus $b$, and they mix the high and low digits in a way neither end does. That is the design idea, and it is a good one as far as it goes. But the end digits do not disappear; they pass into the middle at every step. A number whose last two digits are $00$ has a square whose last four are $0000$, and the middle four digits of that square end in $00$ again — so the low digits carry a property from one step to the next, and the property is absorbing. The traps in the cycle figure are where the end-digit map, running inside the middle-square map, has a fixed point of its own.

Every seed, followed to the end #

The figure follows four seeds, and they show the range of what happens. Seed $6239$ is the longest-lived of all ten thousand: it wanders for 107 steps before it lands on the loop $6100 \to 2100 \to 4100 \to 8100 \to 6100$, and after four more steps a value repeats — 111 steps of usable output. Seed $1234$ wanders for 57 steps and then falls into $0000$, which squares to $00000000$, whose middle is $0000$ again: a trap, from which every later output is zero. Seed $5735$ falls into a different loop of four after 27 steps. And seed $4100$ is on a loop from the start, producing $4100, 8100, 6100, 2100$ and nothing else.

The second figure does the same for every seed at once. For each of the ten thousand four-digit starting values, it counts the steps until some value appears for the second time — the moment the sequence has stopped producing anything new.

The comparison is with the best that any rule of this kind could hope for. A rule that sends each of $N$ values to a single next value is a map, and any map on finitely many values must eventually repeat. If the map were chosen completely at random — each of the ten thousand values sent to one of the ten thousand picked by a fair lottery — the number of steps before the first repeat is governed by the birthday problem. Each new value has a chance proportional to the number of values already seen of being one of them, and the chance of surviving $k$ steps without a repeat is

$$\left(1 - \frac1N\right)\left(1 - \frac2N\right)\cdots\left(1 - \frac{k - 1}N\right),$$

which is the birthday calculation with $N$ days in the year. Its average is close to $\sqrt{\pi N/2}$, about $125$ for ten thousand values, and the line in the figure is that exact distribution.

The middle-square seeds do much worse. Their average is $43.7$ steps, a little over a third of the random map’s, and their distribution is cut off sharply: nothing lasts beyond 111, where a random map would last beyond 200 about one time in seven. The rule does not merely fail to be random. It fails in a specific direction, collapsing faster than chance would.

Where every seed ends #

A finite map’s structure can be described completely: every value either sits on a loop or leads, by a path, into one. The figure below lists every loop of the four-digit rule.

There are only eight. Five are fixed points, numbers that reproduce themselves: $0000$, $0100$, $2500$, $3792$ and $7600$ — and $3792$ is the only one without trailing zeros, since $3792^2 = 14379264$. The other three loops each go round in four steps: $6100 \to 2100 \to 4100 \to 8100$ and the similar $9600 \to 1600 \to 5600 \to 3600$, and one loop with no trailing zeros at all, $0540 \to 2916 \to 5030 \to 3009$. A random map on ten thousand values would typically have its longest loop several dozen steps long; the middle-square map’s longest is four.

The basins are as lopsided as the loops are short. Nearly one seed in five ends at zero. The trailing-zero loops collect most of the rest. The trailing zeros are the mechanism: a number ending in $00$ squares to one ending in $0000$, and the middle four digits of such a square end in $00$ again, so once two trailing zeros appear they never leave, and the sequence is confined to the hundred numbers ending in $00$. The rule leaks into a small subset and cannot climb back out.

Square-root growth, at a third of the length #

Two digits, four, six and eight show whether the shortfall is a quirk of one width or a property of the rule.

Both lines rise with the same slope. Doubling the number of digits squares the number of possible values, and a square-root law turns that into a tenfold increase in the run, which is what the random-map line does exactly and the middle-square line does nearly. At eight digits the middle square averages about 4,465 steps before repeating, against about 12,500 for a random map. The middle square is not failing in a way that more digits would cure. It obeys the birthday law, with a constant about a third as large.

The loops themselves change character with the width. At two digits every seed ends in one of five loops — four fixed points and the pair $24 \to 57 \to 24$ — after at most fourteen steps. At four digits there are eight loops, none longer than four. At six digits there are seventeen, and the longest is a genuine cycle of 210 values, the first one long enough that a short simulation could run inside it without noticing anything wrong; the slowest six-digit seed takes 923 steps to reach a loop. A wider window gives the digits more room to wander before they meet themselves, and the longest loops grow with it, but the growth is the birthday growth and nothing faster. A ten-digit version would on this evidence repeat after something like thirty or forty thousand steps on average — plenty for a calculation that needed a few thousand random numbers and watched for collapse, and hopeless for one that needed a million.

That pattern is the surprising part. The middle-square rule is deterministic arithmetic — squaring and dropping digits — and yet the length of its runs is governed by a probabilistic law, the birthday calculation, scaled down by a constant. The same thing is true of the map $x \mapsto x^2 + c$ modulo a prime, which Pollard’s method uses to find factors exactly because it collides at the birthday rate — and which, for two special values of $c$, fails to behave like a random map for reasons that can be explained by its algebra. The middle-square map is a squaring map read through a window of digits, and it fails in the same kind of way.

Part of the shortfall can be accounted for. A random map has about $63\%$ of the values as somebody’s image, and each image value has, on average, about one value mapping to it, spread out like a Poisson distribution. The four-digit middle square has $61\%$ of values in its image, close to random, but the values that are images are unevenly popular — one is the image of twenty different values — and the rate at which a sequence collides depends on the sum of the squares of those popularities. Putting the measured popularities into the birthday calculation predicts an average run of about 85 steps. The census says 43.7. The remaining half of the shortfall is structure the popularity count cannot see: the trailing-zero traps, which a sequence enters and cannot leave, so that the effective size of the space shrinks as the sequence goes.

The repair: a counter beside the square #

The middle square’s failure is a failure of state. Its whole memory is the current four digits, so the moment one of them repeats, everything after it repeats. The modern repair, proposed by Bernard Widynski in 2017 for 64-bit numbers, adds a second piece of state that cannot repeat quickly: a counter.

The counter advances by a fixed odd amount, not divisible by five, modulo $10^8$, so it runs through all $10^8$ values before repeating — the sequence of multiples of a step that shares no factor with the modulus. Since the counter is part of the state and does not repeat for a hundred million steps, neither can the pair (value, counter), whatever the value does. The output is still the middle of a square, but the square now has the counter added to it, and the traps are gone: no value can be absorbing when something new is added at every step.

The right-hand panel shows the effect on the longest-lived bare seed. The twenty thousand repaired outputs spread across the whole range, they take very nearly the number of distinct values that random draws would, and divided into ten equal ranges they give a chi-squared statistic of $7.8$ on nine degrees of freedom — no sign of unevenness. That is a cure for the collapse and no more than that. Whether the repaired sequence passes the subtler tests — the planes a recurrence cannot leave, the test that ranks the generators — is a separate question, which the 64-bit version has been subjected to and the four-digit toy here has not.

A random map is the ceiling, not the goal #

The comparison is with a random map, not with randomness. A random map is the best a single-value rule can do, and it still repeats after about $\sqrt{N}$ steps — a hundred for four digits. Even a perfect rule of this shape would be useless for serious simulation at small widths, and every random-number rule in practical use has a far larger state for exactly this reason: nineteen thousand bits in the most widely used one. The middle square’s defect is a constant factor on top of a limitation every rule of its kind shares.

The extrapolation to wider windows is an extrapolation. The constant in front of the square root moves between a quarter and a half across the four widths measured, and nothing here says where it settles, or whether it settles at all as the window widens; the ten-digit estimate above assumes it stays near a third.

The eight-digit figures are a sample. Every seed is followed at two, four and six digits, and the statements about them are complete. At eight digits there are a hundred million seeds and the figure follows 400, chosen at random; its average is an estimate, and statements about the longest eight-digit run are not made here for that reason.

The partial explanation is a calculation, not a proof. The birthday calculation with the measured popularities predicts runs of about 85 steps and the census measures 43.7. Attributing the rest to the trailing-zero traps is a reading of the cycle figure, supported by the share of seeds that end in them; it is not a derivation, and no formula on this page predicts 43.7.

Still open: how random a simple rule can look #

The middle-square rule fails its first test, and the counter repairs that failure. What nobody can do in general is prove that a simple deterministic rule passes every test of a given kind. For generators built on number theory there are proofs that predicting the next output is as hard as a problem believed to be hard, such as factoring; for fast practical generators like the repaired middle square, there are batteries of statistical tests and no proofs at all. Donald Knuth tells the cautionary story against his own early attempt: a deliberately complicated generator, designed to be “super-random” by mixing many operations, which on its first run fell almost immediately into a fixed point. Complexity is not randomness, and the census in the second figure is the measurement that says so.

The deeper version of the question is the one the birthday law raises. A deterministic rule whose collisions arrive at exactly the birthday rate is, in that respect, indistinguishable from a random one; a rule whose collisions arrive faster has been caught. For which simple arithmetic maps the collision rate equals the random one, and for which it falls short by a constant as the middle square’s does, there is no general theory — only the census, map by map.