The generator that rounded its own product

The formula sets the power, the sum sets the constant priced the one-pass variance’s error at $\kappa^2 u$ times a constant, where $\kappa^2$ is one plus the mean squared over the variance and the constant belongs to the summation: about $0.4\sqrt n$ for running sums of $n$ values. One dataset refused to sit on that line. The earlier essay cancellation takes the answer, not a digit had drawn its examples from a 31-bit linear congruential generator — the textbook recurrence $s_{k+1} = (a s_k + c) \bmod 2^{31}$ with $a = 1103515245$ and $c = 12345$ — and on a thousand values near $10^6$ with a spread of one, the constant was 48 to 87 on forty-one seeds, with a median of 62, and every one of the forty-one variances came out too large. A well-mixed generator at the same mean and spread gave a median of about 12 and both signs.

The lean sat in the running sum $\sum x_i$, short by 24 to 39 units of roundoff on every seed. The earlier essay named the suspect and did not test it. The low bits of a congruential generator with a power-of-two modulus are famously poor — the lowest bit alternates, the lowest two cycle with period four — and the bits a running sum near $10^9$ discards from each value are its lowest. It predicted, with a sign, that replacing only the lowest five bits of each value with bits from an unrelated generator would remove the lean, bringing the median within a factor of 1.5 of the well-mixed one, and that replacing the top bits would leave it.

Half of that is right. The half that is wrong is more interesting than the half that is right, and it is wrong because the generator in the experiment was never the one the prediction was about.

Five replaced bits make it worse #

The test as stated: take each seed’s thousand states, replace the lowest $k$ bits of every state with bits from the well-mixed generator, form the same values $10^6 + (s/2^{31} - \tfrac12)$, and compute the one-pass variance against the exact variance of those values. At $k = 0$ the constant is the earlier essay’s 62. At $k = 5$ it is 107. Every one of the forty-one seeds still over-estimates.

Replacing the top bits behaves as predicted: three, five or ten of them replaced leave the median at 62 to 65 and every seed on the same side. Whatever produces the lean is not in the leading digits of the values, which is no surprise, since those digits are summed exactly.

But the low-bit curve does not fall. It climbs — 33 at three bits, 58 at four, 107 at five, 185 at six, 225 at seven — and then drops, all at once, between seven and eight: at eight replaced bits the median is 13 and 21 of 41 seeds over-estimate, which is the well-mixed generator’s behaviour to within its own scatter. Nine to twelve replaced bits stay there. The figure further down draws that curve, and the shape it has — a rise to a cliff — is not what a weak bit pattern being diluted would look like. It is what a field of fixed bits being partly randomised looks like, and both halves of that description need explaining.

The recipe is not the recurrence #

The recurrence is integer arithmetic. The recipe the earlier essay ran is not: it is written in a language whose only number is the double, as s = (s * 1103515245 + 12345) % 2147483648. Every state is below $2^{31}$ and the multiplier is just above $2^{30}$, and each fits a double exactly. Their product does not. It can reach $2^{61}$, and a double carries 53 significant bits, so between $2^{60}$ and $2^{61}$ its neighbouring values are 256 apart — the spacing what a float can hold draws as a staircase whose treads widen with every power of two. The product is rounded to a multiple of 256. Then $12345$ is added, which at that size is 48.2 treads, and the sum is rounded again, to 48 treads. Then the modulus is taken, exactly, of a number that has already lost its last eight bits.

The two sequences agree at the first state from seed 1 and part at the second. After that the recipe is its own recurrence: an affine map followed by a rounding to the spacing at whatever size the product happens to be. The exact recurrence’s low byte is itself a full-period congruential generator modulo 256, so it visits every residue once in every 256 steps; a thousand of its states show all 256 low bytes, three or four times each. The recipe’s show fourteen. Seven hundred and eighteen of a thousand states end in eight zero bits: all 506 whose product reached $2^{60}$, and 203 of the 218 whose product fell between $2^{59}$ and $2^{60}$, where the spacing is 128. The rest come from smaller products, with finer spacings, and end in the few residues those spacings and the rounded constant leave behind: 64 on 152 states, 56 on 32, 128 on 58, 192 on thirteen.

That is a generator whose low byte is almost constant, and not quite constant in a lopsided way. For the variance experiment the second fact is the one that matters.

Which way a discarded byte rounds #

A running sum of a thousand values near $10^6$ passes $2^{28}$ at the 269th value and $2^{29}$ at the 537th. From there the sum’s own spacing is $2^{-23}$, while every value lies on a lattice of $2^{-31}$ — the generator’s resolution — so each addition keeps the value’s bits down to $2^{-23}$ and rounds away the eight below them. Those eight bits are exactly the state’s low byte. Rounding to nearest sends a discarded byte below 128 down, one above 128 up, and a byte of zero nowhere: that addition is exact.

So the error each addition makes is fixed by the state’s low byte alone, and the sum’s error is the sum of those. For the exact recurrence the bytes are spread evenly over a full period, and the downward and upward errors cancel to within one tie in every 256 steps. For the rounded recipe, 718 additions in a thousand make no error at all. Of the rest, the largest group — 152 states ending in 64 — rounds down by a quarter of a step, against thirteen ending in 192 that round up by a quarter, and the 56s and 120s round down too. Averaged over all the states, a discarded byte rounds down by twelve units of $2^{-31}$, and the sum is short by twelve units for every value added in the top binade.

The trace says where the lean is made, and it is not made evenly. Until the sum passes $2^{28}$ it discards six bits or fewer from each value; the recipe’s states end in at least six zero bits almost every time, so those additions are exact and the recipe’s line lies on zero, flatter than either honest generator’s. Past the 269th value the seventh bit is discarded, and a state ending in 64 now rounds down by half a step. Past the 537th the whole byte goes, and the line falls at the rate the byte’s average sets. Nine seeds end between $-23$ and $-38$ units of $u$; the exact recurrence and the well-mixed generator end between $-6$ and $+4$.

The direction the error leans measured this kind of accumulation with the rounding mode as the cause: rounding toward infinity gave every error one sign and the total grew in proportion to the count. Here the mode is round-to-nearest throughout, and the data does the same thing to it by presenting the same few bit patterns to be rounded over and over. A one-pass variance then turns a sum that is always short into a variance that is always long, as the earlier essay found, because $\sum x_i$ enters squared and subtracted, and the cancellation the earlier essay measured multiplies the shortfall by $\kappa^2$.

The exact recurrence does not lean #

The direct test of that account is to run the generator the earlier essay meant to run: the same multiplier, the same increment, the same seeds, with the product formed exactly in integer arithmetic.

The lean is gone. The exact recurrence’s constant runs from 0.15 to 19 with a median of 6.3, and 24 of the 41 variances are too large, 17 too small. Its running sum’s error scatters from $-3$ to $+4$ units of $u$. The congruential generator, implemented as a congruential generator, was never the problem; its weak low bits — alternating, short-period, entirely predictable — balance over every period exactly, and a sum that discards them gains as much as it loses.

It is in fact slightly better than the well-mixed generator, whose median on the same lattice is 8.0. That is not a virtue, and the length sweep below makes the reason visible. A full-period low byte cancels by construction where independent bits cancel only on average, so the discarded part of the walk that the earlier essay priced at $0.4\sqrt n$ is shorter for this generator than for a random one. An accuracy experiment that drew its data from it would report a constant a little too small. The generator is part of the experiment either way, and the cleaner statement of the earlier result is that the constant is about $0.4\sqrt n$ for data whose discarded bits are independent — which neither generator’s quite are, and which most measured data is.

Random bits under a fixed field #

That leaves the curve the prediction produced, and the climb in it. Replacing low bits with random ones should have moved the recipe toward the well-mixed generator. It moved it away, by a factor of three and a half at seven bits.

The account above explains it. The sum discards eight bits, and on most of the recipe’s states those eight bits are zero. Replace the lowest $k$ of them with random bits and the discarded byte becomes a random number below $2^k$ — and when $k$ is seven or fewer, every such number is below 128, the half-way point. Every one of those additions rounds down, by half of $2^k$ units on average. Five random bits under three fixed zeros are a biased source of rounding errors, not a neutral one, and the bias grows like $2^k$: 33, 58, 107, 185 at three to six bits. The growth slows at seven because the recipe’s own 64s and 192s are by then overwritten, and stops at eight because the whole discarded byte is random and is as often above the half as below it.

So the prediction asked the wrong question. Whether bits are random is not what decides a running sum’s lean. What decides it is whether the whole field the sum discards is spread evenly over its range, and a field whose top bits are fixed is not, however random its bottom bits are. A correctly rounded value with a little noise in its last digits is an everyday thing — a measurement quantised by an instrument, a decimal stored in binary — and the same arithmetic applies to it whenever the sum’s spacing reaches past the noisy digits into fixed ones.

The dial makes that a prediction rather than a story. A longer sum sits in a higher binade and discards more bits of every value, so the cliff should move with the length — but only as far as the rounding’s damage goes, because above the eighth or ninth bit the recipe’s states carry the recurrence’s own bits, which are spread evenly. At 300 values the sum ends discarding seven bits; the recipe itself barely leans there (median 5.9, 32 seeds over), because most of its additions discard six or fewer and are exact, and replacing three to five low bits creates a lean of up to 60 that ends at seven. At a thousand values the cliff is at eight. At three thousand the sum discards ten bits, the recipe leans the other way on most seeds, and replacing one to seven bits drives every seed under, with constants of 190 to 480; the lean ends between eight and nine. At ten thousand values the sum discards twelve bits, replacing four pushes the constant to 800, and the lean ends at nine. The cliff sits at the narrower of two fields: the bits the sum discards and the bits the rounding damaged.

A lean that changes sign with the length #

The same arithmetic says the recipe’s own lean is not a fixed property of the generator. It depends on which bits the sum is discarding, and that depends on how many values have been added.

At a hundred values the recipe’s constant is 2.2 and its signs are mixed; the sum never discards more than five bits and the recipe’s states have none there to lose. At a thousand it is 62 and every seed is over. At three thousand the median is 87 and only four of fifteen seeds are over; at ten thousand it is 142 and none are; at thirty thousand it is 593. Over that range the constant grows by a factor of 9.5 while $\sqrt n$ grows by 5.5: a bias that accumulates in proportion to the count, as one that always has the same sign does, rather than a walk.

The sign flips because a longer sum discards bits above the low byte, where the recipe’s states are no longer mostly zero, and the residues the spacing leaves at those positions round the other way more often. Nothing about it is a property of the variance formula; the formula only multiplies whatever the sum of the values carries.

The exact recurrence sits below the well-mixed generator at every length from 300 values up, by a factor between 1.2 and 2.8, and below $0.35\sqrt n$ from a thousand values up. That is the full-period cancellation again, at every length the sweep reaches.

What the experiment owed its generator #

Three things follow, and none of them is about the variance.

The first is that a congruential generator in floating point needs its product formed exactly. A 31-bit state times a 31-bit multiplier needs 62 bits, and the double holds 53, so the multiplication must be split — the multiplier into two halves whose partial products each fit, or the arithmetic done in integers — or the generator computes some other recurrence with no period, distribution or independence guarantees at all. The failure is silent: the recipe still produces numbers in the right range, they still look random to the eye, and a histogram of the values would show nothing. Only the low bits give it away, and only to a computation that reads them, which a running sum near a billion happens to be.

The second is that the bits an accumulation discards are a measurement of the data, not of the arithmetic. The order they are added in and three walks and one bound priced a running sum’s error as a walk, with the walk’s $\sqrt n$ coming from rounding errors that take both signs independently. That is an assumption about the discarded digits of the summands, and it fails both ways: a generator whose discarded field is mostly fixed makes errors that share a sign and accumulate like $n$; a generator whose discarded field is a full-period sequence makes errors that cancel better than chance. A coin flip that fixes the average is the deliberate version of restoring the assumption — rounding at random gives every error a fair sign whatever the data supplies.

The third is that a source of test data needs the same scrutiny as the algorithm it is testing. The variation that comes with a seed separated what a seed changes from what the machine changes; here the generator changed what both were measured against. The earlier essay’s sixty-nine was a real property of its data, honestly reported, and its mechanism was a defect in how the data was produced — not weak low bits, but low bits that were not there.

What the replacement test does not show #

The replacement experiment is run on one mean and one spread. At a spread of one the values occupy 31 bits below the binary point and the sum’s binade decides how many are discarded; at a spread of a thousand they occupy ten more bits above it and the same states produce values whose discarded field is a different slice of the state. The cliff should then move by ten bits, and that has not been measured. The account of which residues the rounding leaves is given for products between $2^{59}$ and $2^{61}$ and checked against the low-byte count; the residues from smaller products, which supply the 64s, are counted and not derived one by one.

Still open: a cancellation that lasts, and a multiplier that fits #

A walk that does not grow. The exact recurrence’s low byte balances over every 256 values, so the part of the running sum’s error that the discarded byte makes should be bounded rather than a walk. The prediction with a sign is that at a hundred thousand values the exact recurrence’s error in $\sum x_i$ stays within eight units of $u$ on all nine seeds, while the well-mixed generator’s spreads past twenty on at least three — and that the one-pass constant’s remaining growth with $n$ for the exact recurrence comes from $\sum x_i^2$, whose discarded field is not a congruential sequence.

A multiplier that fits. The minimal standard generator multiplies by 16807 modulo $2^{31} - 1$; its product of a 31-bit state and a 15-bit multiplier needs 46 bits, inside the double’s 53. The prediction is that written the same naive way in double precision it computes its recurrence exactly for every state, that its one-pass constants on forty-one seeds have both signs and a median within a factor of two of the well-mixed generator’s, and that a generator’s safety in floating point is decided by the width of its product alone, not by the quality of its low bits.