Twice the block, half the depth

An octave to land in settled how to carry an eight-bit recurrence past the bottom of its format without losing a bit. The recurrence is detailed balance on a two-well birth–death chain, $\pi_{i+1} = \pi_i\,p_i/q_i$, each product and quotient rounded to E4M3. Beside each stored value sits an integer counter, so the value can be moved by an exact power of two and the counter told how far, the device room for the step, not the value introduced. The rule that worked was a window per step: before step $i$, the value must lie between the smallest normal number divided by $p_i$, so the product does not fall into the subnormal band, and the largest normal number times $q_i/(2p_i)$, so the quotient does not overflow. Hold the value there, rescaling only when it leaves, and the run reproduces an unbounded exponent bit for bit on every depth the chain can be stored at, to 120 octaves of barrier.

That rule pays for its exactness with a counter for every state. A format that already exists pays less: one exponent for thirty-two numbers priced the shared exponent, one scale for a block of values, which is what the microscaling formats do in hardware. The earlier essay asked what sharing would do to its rule, and committed to an answer:

A shared exponent for a block of $b$ consecutive states needs one value of $k$ that lands every state of the block in its own step’s window. The windows are 4.8 octaves wide at the least and the states inside a block span up to about $5b$ octaves on the steep part of a 32-state chain, so the prediction is that blocks of two keep exactness on every depth and blocks of four lose it from about the depth where the steepest four steps span more than 4.8 octaves together.

Both halves of that are wrong, and in opposite directions. Blocks of two fail. Blocks of four survive two to three times deeper than predicted. The quantity that does decide both is the one the prediction named in its first sentence and then replaced with a rougher estimate in its second.

One exponent for each pair, each four, each eight #

The chains are the earlier essay’s, unchanged, and were first built in the well on the far side of the band: a tilted double well, Metropolis rates stored in E4M3, five lengths from 32 to 64 states, every whole depth from two to 120 octaves up to the depth at which a stored rate becomes zero — 91 on 32 states, 115 on 40, beyond 120 on the rest. The comparison is the strict one again: a run either reproduces the unbounded route, the same four significant bits with no limit on the exponent, entry for entry, or it does not.

The rule is the window per step, generalised to blocks. States are taken $b$ at a time from the first. Before the first step out of a block, the rule reads that block’s steps off the stored rates — each state’s distance from the block’s first state is the product of the ratios $p/q$ before it — and asks each state’s step window what it needs of the first state. Intersecting those gives the block’s window: the range of values for the first state from which every state in the block will meet its own step inside its own window. The rule moves the first state by the power of two nearest the middle of that range, and inside the block nothing is moved. The states share the exponent their first was given.

All of this is read from the rates before any value is computed, exactly as the step windows were. With $b = 1$ it is the step rule placing every value at its window’s middle, and on every chain it is exact at every stored depth, which is the control. With $b = 2, 4, 8$ it is one counter for every two, four or eight states.

The figure at the top of the page holds the whole result. Blocks of two fail at 66, 81, 96 and 114 octaves on 32 to 56 states and only the 64-state chain stays exact to 120. Blocks of four fail at 35, 43, 51, 56 and 66. Blocks of eight fail at 23, 23, 27, 32 and 35. The crosses, the depths at which some $b$ consecutive steps first span more than 4.8 octaves, sit at 25 to 49 for blocks of two, 13 to 26 for four and 7 to 13 for eight: left of every dot, by 41 to 71 octaves for pairs, 22 to 40 for fours, 14 to 22 for eights. A rule predicted to fail at 13 octaves on the shortest chain held to 35.

And every dot sits within three octaves of the dashed line. That line is where some block’s window has width below zero: no value of the first state lands every state of that block in its own window. It is exactly what the prediction’s first sentence said the rule needs.

What one block asks of its first state #

The dial shows the mechanism on one chain, 48 states at 60 octaves, where blocks of two are exact and blocks of four are not.

At blocks of two the chain has 24 windows, between 5.0 and 12.7 octaves wide, and every first state lands in the middle of its own. The run is exact, its far well wrong by 2.2 per cent, which is the unbounded route’s own error at four significant bits.

At blocks of four there are twelve windows and four are empty: the blocks that start at states 8, 12, 32 and 36, which cover the steepest descent into the barrier on each side. For those blocks the step windows, shifted back to the first state, do not overlap. The value that suits the block’s first step would put its third or fourth state’s product below the smallest normal number, into the numbers below the smallest one, or its quotient above the largest. The rule does what it can, placing the value at the geometric middle of an interval whose ends are reversed, and four products in that run fall into the subnormal band and one quotient overflows.

At blocks of eight there are six windows and five are empty, by between 1.6 and 17 octaves. Nothing about the rule has changed. What has changed is that each window is now an intersection of eight step windows, and on the steep stretches eight steps descend further than any single step window is wide.

The span against the windows it crosses #

The prediction compared two numbers: the span of $b$ steep steps, about $5b$ octaves, against 4.8 octaves, the narrowest step window anywhere. That comparison is wrong in two ways that pull in opposite directions, and seeing both is the whole correction.

The first error makes the prediction too pessimistic. A block’s window is not the narrowest window less the span. It is the intersection of the block’s own step windows after each is shifted by the distance from the first state, and those step windows are not 4.8 octaves wide. A step’s window runs from the smallest normal over $p_i$ to the largest normal times $q_i/(2p_i)$, each end clipped to what the format stores, so its width in octaves is E4M3’s whole range, 14.8 octaves, less one, plus the base-two logarithm of the smaller of the step’s two rates. On the 32-state chain at 60 octaves the step windows run from 6.8 to 12.6 octaves. The 4.8 the prediction quoted is the narrowest anywhere on any chain at any depth, reached at 75 octaves on 32 states, 95 on 40 and 114 on 48 — deeper than any block of four or eight fails. A block’s states descend through windows two or three times wider than that minimum, and the block window empties only when the descent across the block exceeds those.

The second error would have made it too optimistic, if the first had not swamped it. A block’s span is not $5b$ octaves at a fixed depth: it grows with depth. On the 32-state chain each step’s slope at 60 octaves runs up to six octaves a step, at 30 octaves up to three. The steepest stretch of the chain steepens in proportion to the barrier, and the window it has to fit inside narrows as it does, because a steep step is one whose smaller rate is small. Both move together, so the right comparison is not a fixed span against a fixed width but the two curves against depth.

On 48 states the narrowest window falls almost linearly with depth for every block size, and the slope is the block size. One exponent a state falls from 12.6 octaves at depth two to 4.8 at 120 and never reaches zero, which is why the step rule is exact everywhere. Blocks of two cross zero at 96, blocks of four at 52 and blocks of eight at 26; the runs first fail at 96, 51 and 27. The one-octave line, which decided the single window’s failure in the earlier essay, is crossed five, four and three octaves before those. Here it is not the limit. The likely reason is that the rule places the value at the block window’s middle on every block, not only when it leaves: a window between zero and one octave wide leaves a landed value at most half an octave outside, and the step windows’ factor of two on the high side has room for that.

Twice the block, half the depth #

The straight lines in that figure have a consequence that can be stated without them.

Divide the depth at which each run first fails by the number of states per block, $n/b$. On thirteen of the fourteen combinations of chain length and block size that fail inside the chain, the ratio lies between 4.0 and 4.6 octaves; the fourteenth, blocks of eight on 32 states, four states a block, is at 5.75. For blocks of two it is 4.13, 4.05, 4.00 and 4.07; for four, 4.38, 4.30, 4.25, 4.00 and 4.13; for eight, 4.60, 4.50, 4.57 and 4.38 on the four longer chains. The 64-state chain in blocks of two has 32 states a block and should fail near 134 octaves by the same ratio; it is exact to 120, where the chains stop.

So the depth a shared exponent can carry is about four octaves for each block in the chain. Double the block and the depth halves; double the chain and it doubles. That follows from the shape: a chain of $n$ states descending $d$ octaves into its barrier has steps whose steepest slope is proportional to $d/n$, a block of $b$ of them spans $b$ times that, and the block’s window empties when that span exceeds a step window of roughly fixed width. Only the constant needed measuring, and it is the same constant across a factor of four in block size and a factor of two in chain length.

That is the useful form of the answer. A shared exponent buys back the counter’s storage — one integer for $b$ states instead of one each — and costs depth in exact proportion. On a chain whose barrier is known before it is stored, the block size can be chosen from it: on every chain here, a block size under $4n/d$ is exact at depth $d$, because no first failure came before 4.0 octaves for each state a block holds.

How the larger blocks fail #

The earlier essays drew a sharp line between a run that stops being exact and a run that loses the answer. Past its closing, the single window was a coin: some depths exact, most not, the far well wrong by more than half on nine of the 32-state chain’s depths. Blocks do not fail that way, and how they fail depends on which edge of the window gives.

Below 23 octaves the three lines coincide: every run is exact, and the error, the one the far well in a byte measured, two to twenty per cent, is what four significant bits make of this chain regardless of the exponent: between a tenth of a per cent and nineteen per cent. Past their first failures they separate. Blocks of two on 32 states fail on 23 of 89 depths, every one with products rounded into the subnormal band and none with a quotient past the top of the format, and the far well is wrong by half or more on five of them, at 84 and from 87 to 90 octaves. Blocks of four lose the far well on 46 depths and blocks of eight on 60, and on 41 and 57 of those the run ends in not-a-number.

That is E4M3 speaking. The format has no infinity — one of the rules eight bits, and a format that breaks the rules catalogued — and its top encoding is a NaN, and a quotient past 448 lands there. A block whose window is empty must give up one edge or the other, and the rule’s choice, the middle of a reversed interval, gives up both by about half the deficit each. The product side costs a rounding into the band, which is damage. The quotient side costs the whole vector, because a NaN survives every later multiplication and the normalising sum — the same shape as a norm that overflows before it is a norm, an intermediate past the top destroying an answer the format could hold. On all five chains, blocks of four and eight lose most of their lost depths this way and blocks of two never do.

The same arithmetic was checked against the earlier essay’s own runs, because a lost-depth count that compares an error to one half reports nothing at all for a NaN, which compares false with everything. None of the earlier rules’ runs produced one, so its counts stand. These runs needed the comparison written the other way round.

What the prediction got right #

The prediction’s own first sentence was right: one value of $k$ must land every state of the block in its own step’s window. That is the block window, and its emptying is the line the runs follow to within three octaves on every chain and every block size. What failed was the arithmetic laid over it. Taking the narrowest window from the whole family of chains and depths, and the span from one depth on one chain, compares numbers that never occur in the same block. The first is a property of the deepest, shortest chains near 120 octaves; the second grows linearly with the depth at which it is read.

It is the same mistake the earlier essay found in its own predecessor, made one level up. There, a window’s width was extrapolated to zero, and the measurement said the limit was an octave, not zero, because a rescale moves in octaves — the counter’s version of a bit buys an octave. Here the block window’s width really is the limit — centring at every block buys the half-octave back — but the estimate of when it reaches zero borrowed numbers from the wrong places. A limit read off the data was right both times; a limit assembled from summary statistics of the data was wrong both times.

What five chains and four block sizes do not show #

Every chain here is the same double well at different lengths and depths, so the steepest stretch is always symmetric and always in the same place relative to the wells. A chain with one cliff — a single step far steeper than its neighbours — would put a narrow block window wherever that step falls, and the law of four octaves a block would hold only if the cliff were spread. Blocks are aligned to the first state; a block that straddles the bottom of a well, where the descent turns to ascent, has a smaller span than one on a slope, and an alignment chosen to put block edges at the steepest steps would move each first failure. And the rule reads its block window in binary64. A format that read it in its own arithmetic would round the shifted window edges to four bits, which the factor of two on the high side should absorb, but the runs here do not show it.

Blocks of two first fail at 66, 81, 96 and 114 octaves; the single window of the earlier essay first failed at 66, 81, 96 and 115. Those are different rules with different windows, and nothing above explains why the deepest depth each can carry should agree to an octave on four chains.

Still open: blocks aligned to the slope, the coincidence, and a block in a byte #

Blocks that follow the slope. The law says a block’s span is what empties it. A rule free to choose its block boundaries could put short blocks on the steep stretches and long ones in the wells. The prediction with a sign is that boundaries placed greedily — extend a block until its window would drop under one octave — carry every chain to 120 octaves with a mean of at least three states a block on 48 states and more, so that the depth limit becomes a storage cost rather than a ceiling.

The coincidence at 66, 81, 96. Blocks of two and the single window first fail within an octave of each other on all four chains where both fail. The prediction is that both are bound by the same pair of steps — the steepest descent and the step after it — and that on a chain with an asymmetric tilt, where the steepest steps of the two wells differ, the two first failures separate by more than three octaves.

The block’s exponent in the format’s own bits. A microscaling block stores an eight-bit power of two and nothing else. The prediction is that storing the block’s shift as an E8M0 exponent and reading the block window from E4M3 rates in E4M3 arithmetic changes no first failure by more than one octave, because the block window’s edges are only ever used to choose a whole power of two.