A filter that changes only the spread

The generator with nineteen thousand bits of state ended on a debt. Its output is not its state. Each word the recurrence produces passes through four more lines before it is handed out — shift, mask, exclusive or, four times over — and those lines are called tempering. The essay noted that every modern linear generator has such a step and that none of its figures drew one.

The step is strange on its face. It is a fixed, public, invertible function of each output word, so it cannot hide anything: anyone who sees a tempered word can untemper it. It is linear over the two-element field, like the recurrence, so it cannot make the generator any harder to predict. And it acts on each word by itself, so it cannot change the period. What it does change is visible only when several consecutive outputs are looked at together, and it can be drawn exactly on a generator small enough to run through its whole period.

A twisted generator small enough to finish #

The generator is a scaled-down relative of the Mersenne twister, of the kind Matsumoto and Kurita called a twisted GFSR. Its state is three 8-bit words, $x_0, x_1, x_2$. Each step produces a new word

$$x_{l+3} = x_{l+1} \oplus A(x_l),$$

where $\oplus$ is bitwise exclusive or and $A$ shifts a word one place right and, if the bit that fell off was a $1$, adds a fixed pattern — here the byte $10100110$. The oldest word is dropped, the new one appended, and the word handed out is the one that was oldest.

Everything about it is linear over the field of two elements: each output bit is an exclusive or of some of the 24 state bits. And its period is as long as 24 bits allow. Started from any non-zero state it passes through all $2^{24} - 1 = 16{,}777{,}215$ non-zero states before repeating, which was checked by running it — sixteen million steps is a fraction of a second.

Why the period is as long as it can be is itself a piece of algebra rather than luck. Because every step is linear, the whole generator is a single $24 \times 24$ matrix over the two-element field applied again and again, and its period is the order of that matrix acting on non-zero states. The order is $2^{24} - 1$ exactly when the matrix’s characteristic polynomial is primitive — irreducible, with a root whose powers run through every non-zero element of the field with $2^{24}$ elements. That is the same condition that decided whether a four-bit shift register visited all fifteen non-zero states, and it is the reason every non-zero element of a finite field is a power of one of them. The twist pattern $10100110$ was found by trying patterns until the period came out full.

That is exactly the situation the big generator is in, with 24 in place of 19,937. It has the longest period its state allows, and the question left is how evenly its outputs are spread — not one at a time, where every generator of this kind is fine, but in runs of consecutive outputs.

What “evenly spread” can mean, and its ceiling #

Take the leading $v$ bits of each output and look at $k$ consecutive outputs together. That makes a pattern of $kv$ bits. Over the whole period, the generator is $k$-distributed to $v$ bits if every one of the $2^{kv}$ patterns occurs equally often — except the all-zero pattern, which occurs once fewer because the all-zero state is excluded.

There is a ceiling, and it is a pigeonhole count. The period visits $2^{24} - 1$ states, and each state determines the next $k$ outputs, so at most $2^{24}$ different patterns can ever appear. If $kv > 24$ there are more patterns than states, and some must be missing. So

$$k \le \left\lfloor \frac{24}{v} \right\rfloor,$$

which is the dashed outline in the first figure: 24 outputs at one bit each, 12 at two bits, 8 at three, and so on down to 3 at eight bits. A generator that meets the ceiling at every depth is maximally equidistributed; no generator with 24 bits of state can do better.

Against that ceiling the raw generator is poor. At one bit it is perfect — 24 consecutive leading bits take every value — but from two bits upward it manages only three consecutive outputs at every depth. At eight bits three is the ceiling, so there is no shortfall; at two bits the ceiling is twelve, and the raw generator falls short by nine.

Why three, and only three #

The reason for the three is in the recurrence, and once seen it is obvious.

The raw outputs are the state words themselves, handed out in turn. Three consecutive outputs are the state — all 24 bits of it — so as the state runs over every non-zero value, three consecutive outputs run over every non-zero triple, and any leading bits of them are perfectly spread. That is the three.

A fourth consecutive output is not free. It is $x_{l+3} = x_{l+1} \oplus A(x_l)$, a fixed function of two of the first three. Its leading bits are the leading bits of $x_{l+1}$ added to the leading bits of $A(x_l)$ — and $A$ shifts right, so the second bit of $A(x_l)$ is simply the first bit of $x_l$ moved down one place (the twist pattern has a $0$ there and adds nothing). So the second bit of the fourth output is the exclusive or of the second bit of the second output and the first bit of the first, always. That is an exact relation among the leading two bits of four consecutive outputs, and a pattern whose bits obey a relation cannot take every value: one bit of the eight is fixed by three of the others.

The count makes the defect concrete, and it is not a small unevenness. Half of the possible patterns simply never happen. A simulation that used the leading two bits of four consecutive outputs to choose one of 256 cases would never visit 128 of them, however long it ran. The generator has the longest possible period and passes every test of its outputs one at a time, and it has this hole.

It is the same kind of defect as the planes a linear congruential generator cannot leave, transposed into bits. There, consecutive outputs taken as coordinates fell on a few parallel planes because a whole-number relation tied them together; here, consecutive outputs taken as bit patterns fall in half of the available patterns because a relation over the two-element field ties them together. In both cases each output is fine on its own and the flaw is a linear relation among neighbours, invisible until they are looked at jointly. The difference is that for the congruential generator the relation is built into the recurrence and nothing after it can remove it, while here it lives in which bits are handed out — and that can be changed.

A filter that mixes low bits upward #

The repair is to change what is handed out without changing the recurrence. Instead of $x_l$, hand out $T(x_l)$ for some fixed function $T$ of one word. The period is untouched, because the states are untouched. What changes is which state bits each output bit depends on.

The filter chosen here is the simplest of its kind: a single shift-and-mask step, $y \mapsto y \oplus ((y \ll 3)\,\&\,\texttt{0x50})$. It copies two low bits of the word into two high ones, by exclusive or. Because the bits it reads (1 and 3) are not bits it writes (4 and 6), applying it twice undoes it — it is an involution, a function that is its own inverse — and so it permutes the 256 possible words.

It was found by search. Every filter of this one-step form — seven possible shifts, 255 possible masks — was applied to the generator and its equidistribution measured, and the one with the smallest total shortfall and the fewest mask bits was kept. Filters of the two-step shape the Mersenne twister uses were searched as well and did no better on this small twister. That is also how the real tempering constants were chosen: not derived from a principle, but searched for, and kept because they measured best.

The effect is what the first two figures showed. At two bits the filtered generator is 12-distributed, meeting the ceiling; at three and four bits it reaches 6; the total shortfall across all depths falls from 19 to 4. And the pattern count shows the hole closed: all 256 patterns of four outputs at two bits, each occurring equally often.

The mechanism is the one the diagnosis suggested. The raw leading bits of the fourth output were determined by leading bits of the earlier outputs because the recurrence moves bits down. The filter moves some low-order information up into the leading bits, so the leading bits of each output now depend on parts of the state that the leading bits of its neighbours do not already pin down.

The count is a rank #

Running a whole period and counting patterns is a check, and for a generator with 19,937 bits of state it is impossible. The real criterion is linear algebra, and it is exact.

Each leading bit of each output is an exclusive or of some of the 24 state bits, so it can be written as a row of 24 zeros and ones. Take the $kv$ rows for the leading $v$ bits of $k$ consecutive outputs. The pattern those bits form, as the state runs over all $2^{24}$ values, is the image of a linear map, and every pattern occurs equally often exactly when the map hits every pattern — when the $kv$ rows are linearly independent over the two-element field, which is when their rank is $kv$.

Raw, the rank is 15 out of 24: nine of the rows are combinations of others, which is nine independent linear relations among the leading bits, and each relation halves the set of patterns that can occur. Tempered, the rank is full. The pattern count in the earlier figure is the same fact seen from the other end — $2^7 = 128$ patterns present at four outputs, because the rank there is 7 rather than 8.

This is how equidistribution is verified for the Mersenne twister itself. Nobody runs a period of $2^{19937} - 1$; the rank of a $kv$-by-19,937 matrix over the two-element field is computed instead, and the famous claim that the generator is 623-distributed to 32 bits is a statement that certain such ranks are full. It is the same kind of exact, finite, linear-algebra certificate as the lattice test for linear congruential generators, and it has the same virtue: a property of the whole period, decided without generating any of it.

A control, and a picture that shows nothing #

A filter that changed every measurement would be suspect, so it is worth checking a case where it has nothing to do.

Two consecutive outputs are two of the three state words, so any leading bits of them are spread perfectly with or without the filter. The filter is invertible, so it cannot spoil that, and the count confirms it. The improvement lives exactly where the diagnosis put the defect — in runs longer than the state’s three words — and nowhere else.

The raster is the honest counterpart. Laid out as bits the raw and tempered streams are indistinguishable to the eye, and no amount of staring at either would reveal that one of them never produces half of the 256 four-output patterns. The defect is a joint property of several outputs across a whole period, and pictures of a stretch of output are the wrong instrument for it — which is precisely why generators are certified by rank computations and tested by batteries rather than inspected.

What tempering cannot do #

It cannot make the generator unpredictable. The filter is linear and invertible, so each tempered output reveals exactly as much about the state as a raw one. Recovering the rule from a linear generator’s outputs is untouched by it: untemper the outputs — the filter is its own inverse here, and the Mersenne twister’s four steps are inverted in a few lines — and solve the linear system as before. Tempering is an equidistribution device and nothing more, and a generator whose seed is needed secret must get its security elsewhere.

It cannot raise the ceiling. The pigeonhole bound $\lfloor 24/v \rfloor$ depends only on the size of the state. A filter chooses which bits are looked at; it cannot conjure patterns that the state is too small to hold. That is why generators aimed at high-dimensional work have large states, and why tempering is paired with a large state rather than used instead of one.

It cannot remove linearity from the bit stream. Every output bit is still a linear function of the state, so the sequence of any single output bit satisfies a linear recurrence of length at most 24 here — 19,937 for the twister. Statistical tests that measure linear complexity, or the rank of large binary matrices built from the output, detect that and fail every generator of this family however it is tempered. The standard test batteries report exactly those failures for the Mersenne twister.

What the pictures cannot show #

The generator is small by design, so that its period can be run to the end and every claim checked by counting as well as by rank. The claims about the Mersenne twister rest on rank computations that no picture here reproduces, and the figure of a 24-by-24 matrix stands in for a matrix with nearly twenty thousand columns.

The search that found the filter is described, not drawn: 1,785 candidate filters were measured and one kept. Several tie with it, and a different generator of the same size would need a different filter — the constants belong to a particular recurrence, which is why the twister’s tempering constants mean nothing when copied onto another generator.

And no figure shows whether the improvement matters. Equidistribution in the leading bits guarantees that certain uses of the output are unbiased over a full period; a given simulation uses a tiny fraction of the period and may not depend on those bits at all. The theory says what is guaranteed; which applications need the guarantee is a separate and much less tidy question.

Still open: how close to the ceiling a fast generator can get #

After the Mersenne twister, the aim became generators that meet the ceiling at every depth — maximally equidistributed — while staying fast. Panneton, L’Ecuyer and Matsumoto’s WELL generators of 2006 achieve it for large states by building the equidistribution into the recurrence rather than repairing it afterwards, and faster variants trade some of it back for speed. Whether a generator can be simultaneously maximally equidistributed, extremely fast, and free of the linearity that the complexity tests detect is not settled, because the last requirement pushes towards non-linear designs where none of the rank theory applies. The theory of this path has been almost entirely linear; its open frontier is what can be proved about generators that are not.

A permutation of the output, and what it bought #

Tempering is a permutation of the output words, chosen by search, that reads a few low bits and writes them into high ones. It leaves the state, the period, the linearity and the predictability exactly as they were. On the small twister in the figures it turns an output in which half of all four-output patterns never occur into one in which every pattern occurs equally often, and it does so by changing nothing except which state bits each output bit depends on.

That is a narrow service and an exact one. It is certified by a rank over the two-element field, it can be undone by anybody, and it is the last thing done to the numbers before the most widely used generator hands them to a simulation.