Error in a Long Sum Grows Like Root n, Not Like n

Last timeThe Error of One Operation

The bound on a sum of a million values allows 999,999 unit roundoffs of error, the measured error is 169, and they differ because the roundings have mixed signs unless something makes them agree.

What a long sum is allowed to do

One addition rounds once and is wrong by at most half the gap at its result. A

sum of $n$ values is $n - 1$ additions, so there are $n - 1$ roundings, and the

question is what they do together. Write $s_k$ for the running total after $k$

terms, with $s_1 = x_1$ and $s_k = \mathrm{fl}(s_{k-1} + x_k)$ at every later

step. The model for one operation applies to each step on its own, giving

$s_k = (s_{k-1} + x_k)(1 + \delta_k)$ with $|\delta_k| \le u = 2^{-53}$ , where

$\delta_k$ is the relative error of that one addition and $u$ is the unit

roundoff, $0.00000000000000011102230246251565$ .

Now the step that usually gets skipped. The factor $1 + \delta_k$ does not

multiply $x_k$ . It multiplies the entire quantity $s_{k-1} + x_k$ , which is to

say it multiplies everything added so far. So the error committed at the second

addition is carried into the third, and into the fourth, and into every

addition after that. Unrolling the recursion and discarding the products of two

or more $\delta$ s, which are smaller than $10^{-32}$ and cannot matter at this

size, leaves the error of the finished sum as a weighted total of the

individual roundings, each weighted by the running total at the moment it

happened.

FIG 1The error of a sum, and the bound that follows

: the total the machine returns after n minus 1 rounded additions
: the exact mathematical total of the stored values, with no rounding anywhere
: the relative error of the kth addition alone, a definite number of either sign with magnitude at most u
: the running total after k terms, which is what the kth rounding acts on
: the worst case, reached only if every one of the n minus 1 roundings is as large as it may be and all of them have the same sign

The bound replaces every partial sum by the sum of all the magnitudes, which is the largest any partial sum can be, and every delta by u. Two consequences are worth reading off before any numbers arrive. The bound is proportional to the sum of the magnitudes rather than to the answer, because the roundings act on the running totals. And the early terms carry the most weight, since they sit inside every partial sum that follows them.

The worst case, as a number

Take a million values drawn uniformly between 0 and 1. Their total, computed

exactly and rounded once at the end, is 499,984.11193900305. The terms are all

positive, so the sum of the magnitudes is the total itself, and the bound reads

$999{,}999 \, u S$ . In relative terms that is

$999{,}999 \times 0.00000000000000011102230246251565 =

0.00000000011102219144021319$, and in absolute terms it is 0.0000555, so the

bound guarantees only the first ten digits of a sixteen digit format.

Adding the same million values left to right gives 499,984.11193899205. The

error is $-0.0000000110012$ , which in units of $uS$ is $-198.19$ . The bound

allowed 999,999 of those units. The measurement used 198, so the bound is too

large by a factor of $999{,}999 / 198.19 = 5{,}046$ . A reader told only the

bound would conclude that a million additions destroy six digits, try it, see

that it destroys two, and stop believing the page.

What the error actually does as the sum gets longer

The way to settle this is to lengthen the sum and watch. Each row below is the

mean of twenty independent data sets, so that one lucky arrangement cannot

decide the shape, and the error is reported in units of $uS$ so that the rows

are comparable.

The lesson stops here

7 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