An octave to land in

Room for the step, not the value carried an eight-bit recurrence with an integer beside each stored value, so that the value could be moved by an exact power of two whenever it neared an edge of the format, and found that the right thing to watch was not the value but the operation about to be done to it. 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 the format. A window read off the chain’s stored rates — no lower than the smallest normal number divided by the smallest $p$, so that no product falls into the subnormal band, and no higher than the largest normal times the smallest $q$ over twice the largest $p$, so that no quotient passes the top — reproduced the same significand with no exponent limit, bit for bit, on all 531 runs of every format to sixty octaves of barrier.

The window narrowed as the barrier deepened, and on the shortest chain in E4M3 its width was falling about a fifth of an octave for every octave of barrier. The essay extrapolated and made a prediction with a sign: the 32-state line “meets zero near 67 octaves”, and “the window rule’s runs stop reproducing the unbounded exponent at the depth where the computed width first goes negative, to within one octave, and the aiming rule’s do not — a chain built past sixty octaves is the test.”

The chain can be built to 120 octaves without changing anything else, so the test is direct. Both halves of the prediction fail, and the way they fail says what a rescaling rule actually needs from the format.

Chains past sixty octaves #

The chains are the ones the well on the far side of the band built: a double well $\sin^2(\pi s)$ with a slight tilt, Metropolis rates with proposal one half, a temperature chosen so the top of the barrier is $2^{-d}$ of the near well, and the rates stored in E4M3 before anything is computed. Five lengths, from 32 to 64 states, and every whole depth from two to 120 octaves. The comparison is the strict one: a rescaled run either reproduces the unbounded route — the same four significant bits with no limit on the exponent — entry for entry, or it does not.

Past sixty octaves something happens to the chain that did not happen before it, and it has to be read before any rule is. E4M3’s smallest normal number is $2^{-6}$, and its subnormals go down to $2^{-9}$ in steps of $2^{-9}$ — the band that eight bits, and a format that breaks the rules measured at three octaves wide. A deeper barrier on the same number of states means steeper steps, and the uphill rates fall with them: on the 32-state chain the smallest stored $p$ is $2^{-7}$ at sixty octaves, $2^{-8}$ at 68, $2^{-9}$ at 75. At 91 octaves a rate falls below half of $2^{-9}$ and is stored as zero. From there the chain in the format is a different chain — one with a wall in it — and no treatment of the exponent can compute a far well the stored rates have cut off. On 40 states the same happens at 115 octaves; on 48, 56 and 64 it does not happen inside 120.

That is the last limit, and it belongs to the data rather than to the arithmetic. Every rule below is judged on the depths before it.

The figure at the top of the page is the whole result in one place. On every chain where the window closes inside 120 octaves, the window rule’s first failure, the blue dot, sits to the left of the dashed line where the width goes negative and to the right of the dotted line where it falls under one octave. The aiming rule’s first failure, the violet dot, is never far from the dashed line either, on one side or the other. And the pale bar, the third rule, runs unbroken to the end of every chain.

A width that is still positive #

The window rule fails first at 66 octaves on 32 states, 81 on 40, 96 on 48 and 115 on 56. The width goes below zero at 68, 85, 103 and 120. So the rule stops being exact two, four, seven and five octaves before the depth the prediction named, outside its tolerance of one on every chain. At the depth where each first fails, the window still has 0.39, 0.39, 0.71 and 0.39 octaves of room in it.

The reason is in what a rescale is allowed to do. It multiplies the stored value by $2^k$ for an integer $k$ and adds $k$ to the counter, which is what makes it exact: a normal number times a power of two is the same significand with a different exponent. But it means the value can only be moved in whole octaves. A window narrower than an octave need not contain any of the positions a given value can be moved to. The value $v$ and the window $[\ell, h]$ fix the value’s position within its octave, and if that position falls outside the window’s fraction of the octave, no integer $k$ puts $v \cdot 2^k$ inside.

The first failure on 32 states is exactly that. At 66 octaves the window runs from 2.67 to 3.5. The value arriving at the seventh state is 2.5, below the window. The rule computes the shift that brings it nearest the window’s geometric middle, which is zero octaves — doubling it would give 5, further from the middle than 2.5 is and outside the window on the other side. So the value stays at 2.5 and meets the steepest descent step of the chain, whose stored $p$ is $3 \cdot 2^{-9}$. The exact product is $7.5 \cdot 2^{-9}$, a sixteenth below the smallest normal, and the band’s grid is $2^{-9}$ wide, so it rounds to $2^{-6}$. With no exponent limit, $7.5 \cdot 2^{-9}$ is $1.875 \cdot 2^{-7}$, which four significant bits hold exactly. The two runs differ from the seventh state on.

The general statement is short. A window guarantees exactness for every value inside it, and a rule built on it guarantees exactness only if it can always put the value inside. With moves in whole octaves that needs an octave of room, not a positive width. The dotted line at one octave is where the guarantee lapses: 63 octaves on 32 states, 79 on 40, 95 on 48, 111 on 56. Every first failure sits between that line and the zero line, which is the measurement saying the width that matters is one, not zero.

Past the first failure, a coin #

A guarantee lapsing is not the same thing as a computation failing, and past its first failure the window rule is neither exact nor wrong in any steady way. On the 32-state chain it fails on 20 of the 25 depths from 66 to 90 and reproduces the unbounded exponent on the other five — at 67, 68, 72, 73 and 74 octaves, three of them past the depth at which its width is negative.

The dial shows why a negative width is not fatal everywhere. The one window is a single interval that must suit every step of the chain at once: its lower end is set by the smallest $p$ anywhere, which belongs to the steepest step on the way down into the barrier, and its upper end by the largest $p$ and the smallest $q$, which belong to the gentle steps and the steepest step on the way up. Its width is the format’s range less those octaves: $\log_2(448) + 6 + \log_2 q_{\min} + \log_2 p_{\min} - \log_2(2\,p_{\max})$, with $p_{\max}$ a half. No single step pairs those three rates. A value that sits a little outside the one window is usually still inside the window the next step actually needs, which is the shaded band.

So at 72 octaves the one window is 0.61 octaves negative and the rule is still exact. Four of its products even fall into the band there, and all four happen to lie on the band’s grid, which a product with few significant bits often does; the steps where the value sits outside the one window are mostly not the steps whose rates set its bounds. At 76 octaves, the dial’s second stop past the zero line, it is not: four products fall into the band, the far well comes out wrong by 26 per cent where the unbounded route is wrong by 7.2. At 84 octaves the window is 3.2 octaves negative, the rule’s lower end is above its upper end, and every step rescales the value to the same place — the flat red line — which is the right place for no step in particular. Six products fall into the band and four quotients reach 448, and the far well is wrong by 88 per cent.

One more thing the dial shows, at 66 octaves: a run that is not exact is not necessarily a worse run. The single product rounded on the band’s grid at the seventh state happens to move the far well towards the double-precision answer, and the far well is wrong by one per cent where the unbounded route, and the step rule with it, are wrong by twenty. That is luck, in the same sense that the far well in a byte warned against reading a survival count that had been passed by a different sequence of roundings: the reference here is the unbounded exponent, and the only claim a rescaling rule can make is to reproduce it.

The aim needs room above #

The second half of the prediction was that the aiming rule would not close. It rescales before every step so that the product $p_i v$ lies between one and two, and the previous essay said it “needs only that each rate and each rate’s reciprocal is representable”. Read literally, that is true. What it misses is where the rule puts the value in order to aim the product.

To put $p_i v$ between one and two the rule sets $v$ between $1/p_i$ and $2/p_i$. On the steepest descent step of a deep chain, $p_i$ is a few times $2^{-9}$, and $2/p_i$ is several hundred. E4M3’s largest normal number is 448. Once twice some rate’s reciprocal passes 448, there are steps on which the value the rule aims for does not fit, and the rescale that was meant to be exact saturates instead. That happens at 68 octaves on 32 states, 85 on 40, 103 on 48, and 120 on 56 — by coincidence of how these chains’ rates fall, the same depths at which the one window’s width goes negative.

The aiming rule’s first failures follow it: 69 octaves on 32 states, 92 on 40, 108 on 48, and none inside 120 on 56. On the shortest chain it fails three octaves after the window rule does. It is not a gentler failure either: once its rescale saturates, the counter records a power of two that was not applied in full, and every later entry inherits the difference.

Below 66 octaves the three lines are one line, because all three rules reproduce the unbounded route. Past it they separate. Over the 89 depths at which the 32-state chain is stored, the aiming rule loses the far well on 16 and the one window on nine. The aiming rule’s losses are the worse: from 80 octaves on its far well is wrong by more than ninety per cent, because the value it saturates is the value at the bottom of the barrier, and the whole far well is assembled from what is carried out of it.

That the aiming rule is the worse of the two inverts the earlier ranking, and the inversion is the instructive part. Aiming was the rule that could not miss the band, and it does not: no product of an aiming run ever falls below the smallest normal. It fails at the top, exactly as the floor rule failed at the top on the climb out of a sixty-octave barrier — and for the same reason, a placement that leaves no room for the operation’s reach. Holding the product at one pins the value at the reciprocal of the rate, and the reciprocal of a small rate is a large number in a format whose largest number is 448. A norm that overflows before it is a norm made the same mistake impossible by keeping room for the square rather than for the value; aiming keeps room for the product and none for the quotient.

A window for each step #

The repair follows from both failures. The one window has to suit every step at once; the aiming rule suits one step but chooses a position without regard to the format’s top. What each step needs is a window of its own: $v$ no lower than the smallest normal over $p_i$, so that this step’s product is normal, and no higher than the largest normal times $q_i$ over $2p_i$, so that this step’s quotient stays an octave clear of the top — intersected with the format itself. Before each step the rule checks the value against that step’s window and rescales to its middle only when the value is outside.

The width of the step’s window is the format’s normal range less one octave, plus $\log_2 q_i$. The smallest rate E4M3 can store that is not zero is $2^{-9}$, so no step’s window is ever narrower than $14.8 - 1 - 9 = 4.8$ octaves, which is far more than the one octave a rescale needs to land in. Measured, the narrowest step window on any chain is 4.81 octaves, on 32, 40 and 48 states alike, because all three reach a rate of $2^{-9}$.

That makes the rule’s guarantee unconditional on everything except the chain’s storage. It reproduces the unbounded exponent on every depth of every length at which no stored rate is zero — 89 depths on 32 states, 113 on 40, 119 on the others — and on E5M2 and half precision on every depth to 120, where nothing closes at all. On the 32-state chain it keeps the far well at every depth to 90 octaves, wrong by at most 26 per cent, which is the four bits’ own error and the same error the unbounded route makes. The numbers below the smallest one opened this question with a format whose band was worth a few octaves; with a window per step, the band is never visited.

The exact rule is also the cheapest #

It would be reasonable to expect exactness at every step to cost a rescale at every step, as the aiming rule’s does. It costs less than the other two rules. On 32 states the window per step averages 12.6 rescales a run against 19.2 for the one window and 26.8 for aiming; on 64 states 17.3 against 27.8 and 50.7. The aiming rule rescales almost every step because it insists on one position. The one window rescales more often as it narrows, because a narrow window is left by any step of more than its own width, and past its closing it rescales every step to a point that suits none. The window per step is wide everywhere and only acts when a step is about to go wrong.

Every rule makes one comparison a step, so the comparisons are the same price. What the step window adds is its two bounds per step, which can be computed once from the stored rates before the recurrence starts and kept beside them: two more numbers a rate, in a computation whose rates are already an array. That is a storage cost the one window does not pay, and it is the only one.

What the closing was made of #

Three limits were folded into the earlier essay’s extrapolated sixty-seven octaves, and they come apart once the chain is built.

The first is the rule’s resolution. A rescale moves in octaves, so any rule that holds a value in an interval needs the interval to be an octave wide, and the one window reaches that width two to seven octaves before it reaches zero. This is the same lesson as a bit buys an octave read the other way round: there a shared exponent’s resolution was set by the significand, here a counter’s is set by the integer it adds.

The second is the rule’s choice of position. A window shared by every step is set by rates that never meet in one step, and a position aimed at one operand ignores the other. Neither is a limit of the format; both are limits of the rule, in the sense the units that overflow before the answer does meant when it found an intermediate needing more range than its result.

The third is the format’s, and it is the only one left with a window per step. E4M3 cannot store a rate below half of $2^{-9}$, and a chain steep enough to need one has a stored zero in it. Past that depth the question is no longer how to compute the stationary vector of the chain but whether the chain has been stored at all. What a float can hold drew the format’s numbers; the last of them is where this computation ends.

What 559 chains do not show #

Five chain lengths and 119 depths are 595 runs a rule; without the depths at which a rate is zero, 559 remain, and every one is a single chain of a single shape. The rates of a double well are smooth along the chain, so neighbouring steps have similar windows and a value rescaled into one step’s window is rarely far outside the next one. A recurrence whose multipliers jump from step to step would make the step window rescale more often, though its guarantee — four octaves of room per step at the least, whatever the rates — is a statement about each step separately and does not depend on smoothness. The coincidence of the aiming rule’s room with the one window’s zero is a property of these chains, not a theorem, and the count of rescales is an average over depths and so weighted toward the deep, steep chains where every rule works hardest.

Still open: rates with an exponent of their own, a block that shares one, and a certificate in a byte #

A counter for the rates. With a window per step the chain’s own storage is the only limit left, and it is the same kind of limit the value had: a rate below the band is lost because it has no exponent to spare. Storing each rate as a significand and an integer, as the value is stored, removes it. The prediction with a sign is that a 32-state chain carried that way reproduces the unbounded exponent on every depth to 120 octaves, that its far well is lost only where the unbounded route loses it — on no more than three depths in a hundred — so that the depth at which E4M3 can carry this chain is set by its four bits alone and not by any exponent, the value’s or the rates’.

One exponent shared by a block. The previous essay’s first question is still unasked, and one exponent for thirty-two numbers is where the shared exponent was first priced. With the step window as the rule, 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.

A certificate in a byte. The componentwise backward error of an E4M3 run with a counter is a statement about a computation whose only error is its four bits. Whether that number can tell a far well wrong by eight per cent from one wrong by a quarter — the range this page’s unbounded runs span — decides whether such a vector can be shipped with any statement of its accuracy, and it is now the only one of the three questions this chain has asked four times without an answer.