One Rounding Is Half a Gap, and a Tenth Plus Two Tenths Is Exactly a Tie

Last timeThe Gaps Between Representable Values

The error of a single floating point operation is at most half the gap at its result, one part in two to the 53, and a tenth plus two tenths lands exactly on a midpoint.

What one operation is allowed to do

The rule for a single arithmetic operation is short enough to quote. Take the

two stored values exactly as they are, compute the exact mathematical result,

and return the representable value nearest to it. Addition, subtraction,

multiplication, division and square root are all defined this way, and a

machine that returns anything else is not conforming.

So there is no sloppiness in one operation and no drift that depends on which

machine ran it. But the exact result usually is not representable, so what

comes back is the nearest value that is, and that difference is the error.

That difference has a size, and the size is already fixed by the layout. Write

$g$ for the distance between neighbouring representable values, which for a

64 bit value in the interval from $2^{e}$ up to $2^{e+1}$ is $g = 2^{e-52}$ ,

since the significand holds 52 stored bits after an implied leading one. An

exact result landing anywhere in that interval is at most $g/2$ from the nearer

of the two values bracketing it, because a point further than half the spacing

from both would have to lie outside the interval they bound.

FIG 1The error of a rounding, as the value being rounded moves

rounded to one decimal place, a step of 0.1

Rounding to one decimal place is the same mechanism with a step of 0.1 instead of a power of two, and it is drawn here because a step of two to the minus 52 cannot be drawn. The error is a sawtooth running from minus 0.05 to plus 0.05 and resetting at every midpoint. Half the step is not an average or a typical case: it is the edge the sawtooth reaches and never crosses, and it is reached at every midpoint between two representable values.

The error is bounded not because somebody was careful but because there is

nowhere further than half a step to be, and it is a deterministic function of

the input rather than a random disturbance, which is the fact that decides how

a long calculation behaves.

Half a gap, as one number that works everywhere

A bound of $g/2$ is awkward to carry around because $g$ depends on where you

are. Divide it by the magnitude and the dependence vanishes. For $x$ in the

interval from $2^{e}$ to $2^{e+1}$ the gap is $2^{e-52}$ , half of it is

$2^{e-53}$ , and the magnitude is at least $2^{e}$ , so the relative error is at

most $2^{e-53}/2^{e} = 2^{-53}$ . The exponent cancels. One constant, called the

unit roundoff, therefore covers every magnitude the format reaches.

The lesson stops here

9 more paragraphs to go

You have read the opening. The rest of the argument, the problems that check whether it landed, and the lines worth keeping at the end all come with a plan.

The first lesson of every course in the library reads the whole way through, free, so you can see exactly what the rest of them are.

See the plan The contents

This is the reading half

Starting the course gives you your own copy of it. Every idea on every page has problems standing under it, marked with a reason rather than a tick, and any sentence you do not believe can be opened and argued with. None of that can happen on a page nobody owns.

The contents

One Rounding Is Half a Gap, and a Tenth Plus Two Tenths Is Exactly a Tie

What one operation is allowed to do

Half a gap, as one number that works everywhere

9 more paragraphs to go

This is the reading half

Read alongside