Round-off Error

1. Context

Round-off error arises when a real number, or the result of an arithmetic operation, is rounded to finite-precision floating-point. Under the default round-to-nearest mode, the relative error of a single rounding is bounded by the unit roundoff $u = \varepsilon_{\text{mach}}/2$ (where $\varepsilon_{\text{mach}}$ is machine epsilon), but over many operations the accumulated error can become non-negligible.

For the definition, generation mechanism, and rounding modes, see the earlier chapters. This chapter focuses on quantitative accumulation analysis and reduction techniques.

Below, in expressions for the order of error, we write $\varepsilon_{\text{mach}}$ simply as $\varepsilon$ (inside $O(\cdot)$ the factor-of-2 difference from $u$ is absorbed into the constant).

2. Accumulation Models

Random Walk Model

Assuming round-off errors are random and independent over $n$ operations, the cumulative error grows as

(random walk). In practice, error signs tend to fluctuate somewhat randomly, so many computations exhibit behavior close to this model.

Here $E$ is the relative error of computing the sum $S = \sum_i a_i$ of $n$ numbers, namely the error $|\hat{S} - S|$ divided by $\sum_i |a_i|$. The relative error with respect to $|S|$ can be much larger when positive and negative terms cancel (see avoiding catastrophic cancellation in §3).

Worst Case

When errors always accumulate in the same direction:

This worst case gives the error bound of naive sequential summation. On real data, however, the error signs fluctuate, so the behavior is usually close to the random walk above; growth proportional to $n$ appears only for data constructed so that all roundings go the same way.

3. Summation Algorithm Comparison

When computing $\displaystyle S = \displaystyle\sum_{i=1}^{n} a_i$ for $n$ floating-point numbers, algorithm choice dramatically affects the accumulated error.

Kahan Compensated Summation

Accumulates the fractional part lost to rounding in a compensation variable, correcting at each step. See Loss of Significance for pseudocode and details.

Pairwise Summation

Recursively splits the array in half and sums each half. Only $\log_2 n$ addition levels are needed, bounding accumulated error at $O(\log n \cdot \varepsilon)$.

function pairwiseSum(a[], lo, hi):
    if hi - lo < 16:          // base case: naive sum
        s = 0.0
        for i = lo to hi-1: s += a[i]
        return s
    mid = (lo + hi) / 2
    return pairwiseSum(a, lo, mid)
         + pairwiseSum(a, mid, hi)

Other Techniques

• Avoiding catastrophic cancellation: Transform formulas to avoid subtraction of nearly equal values.
• Higher precision: Use quadruple or arbitrary precision when double precision is insufficient.
• Choosing stable algorithms: Prefer backward-stable algorithms.

4. Trade-off with Truncation Error

The two main sources of error in an algorithm are round-off error and truncation error (errors in the input data and modeling errors are considered separately), and the overall error is roughly estimated as their sum. In many situations, improving accuracy causes round-off error to grow, so an optimal parameter exists.

Numerical Differentiation Example

Consider the forward difference $f'(x) \approx \dfrac{f(x+h) - f(x)}{h}$.

• Truncation error (Taylor remainder): $\dfrac{h}{2}|f''(\xi)| = O(h)$ — decreases as $h$ shrinks.
• Round-off error: $f(x+h)$ and $f(x)$ each carry rounding error $O(\varepsilon |f(x)|)$, proportional to the size of the function value. The difference $f(x+h)-f(x)$ retains error of this size, and dividing by $h$ amplifies it to $O(\varepsilon |f(x)|/h)$.

Minimizing total error $E(h) \sim C_1 h + C_2 \varepsilon/h$ gives optimal step $h^* = \sqrt{C_2\varepsilon/C_1}$; smaller $h$ actually degrades accuracy. Here $C_1 = |f''(\xi)|/2$ and $C_2 \approx 2|f(x)|$ (since the rounding errors of $f(x+h)$ and $f(x)$ are each about $\varepsilon|f(x)|$; the constant also depends on how the function is computed, so it is only a guide), so $h^*$ depends on the function. If $|f(x)|$ and $|f''(x)|$ are comparable, $h^* \approx 2\sqrt{\varepsilon} \approx 3 \times 10^{-8}$ (double precision); roughly, $h^* \sim \sqrt{\varepsilon} \approx 10^{-8}$ in order of magnitude.

The figure below plots $E_{\text{trunc}}=C_1 h$ (blue), $E_{\text{round}}=C_2\varepsilon/h$ (red), and total error (green) on a log-log scale. The two lines cross at the optimal $h^*$, where total error reaches its minimum.

Series Truncation

Truncating the Taylor series to the finite sum $e^x \approx \displaystyle\sum_{k=0}^{N} x^k/k!$ also exhibits a trade-off.

• Truncation error: $O(|x|^{N+1}/(N+1)!)$ — decreases rapidly as $N$ increases.
• Round-off error: $N$ additions → $O(N\varepsilon)$ accumulation (§2 model).

Unless $|x|$ is large, the terms of the series for $e^x$ decrease rapidly ($|x|^k/k!$ starts to decrease once $k$ exceeds $|x|$), so round-off accumulation is typically not a concern at practical $N$ (a few dozen terms). The more serious issue is catastrophic cancellation when computing $e^{-x}$ ($x>0$) via $\displaystyle\sum (-x)^k/k!$, which requires reformulation such as $e^{-x}=1/e^x$ (though for very large $x$, $e^x$ itself overflows, requiring a different approach).

5. Frequently Asked Questions

6. References

• Wikipedia, "Round-off error"
• Wikipedia, "Kahan summation algorithm"
• Wikipedia, "Pairwise summation"
• N. J. Higham, Accuracy and Stability of Numerical Algorithms, 2nd ed., SIAM, 2002, Chapter 4 (Summation).
• D. Goldberg, "What Every Computer Scientist Should Know About Floating-Point Arithmetic," ACM Computing Surveys, vol. 23, no. 1, pp. 5--48, 1991.