Skip to content
Tutorials Center
My learning

Topics

Lesson 7 of 37 · Errors and Floating Point

Rounding Error and Cancellation

See how small rounding errors grow into big ones: catastrophic cancellation, summation order, Kahan summation, and how to rewrite formulas to avoid losing digits.

Each floating-point operation makes a tiny relative error, about 1e-16. That sounds harmless, and most of the time it is. But in a few situations those tiny errors are amplified into answers with no correct digits at all. The most famous culprit is catastrophic cancellation: subtracting two nearly equal numbers.

This lesson shows you how to recognise the dangerous patterns and how to rewrite formulas so that the digits survive. These skills matter in every later chapter, from derivative formulas to linear systems.

Catastrophic cancellation

Suppose two numbers are known to 16 digits and agree in their first 12 digits. Their difference has only about 4 meaningful digits left, because the leading digits cancel and what remains is dominated by the old rounding noise.

Take f(x) = (1 - cos(x)) / x^2. As x → 0 the true value tends to 0.5. Evaluate it with small x:

Python Cancellation in 1 - cos(x)

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The results drift away from 0.5 and become exactly 0 for tiny x, because cos(x) rounds to 1.0 and the subtraction wipes out everything. The fix is algebraic: use the identity 1 - cos(x) = 2 sin²(x/2), which has no subtraction of nearly equal numbers.

Python Rewrite the formula to avoid cancellation

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The stable version returns 0.5 for every small x. The two formulas are mathematically identical but numerically very different, which is the central lesson of this whole subject.

The quadratic formula trap

The roots of a x² + b x + c = 0 are (-b ± sqrt(b² - 4ac)) / 2a. When b² ≫ 4ac, sqrt(b² - 4ac) is almost |b|, and for one of the two signs the numerator subtracts two nearly equal numbers.

The cure is to compute the safe root first, q = -(b + sign(b) sqrt(disc)) / 2, and get the other from the product of roots c / a:

Python A stable quadratic solver

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The naive small root has only a few correct digits (or none). The stable method gets both to full precision. Similar rewrites exist for many formulas: sqrt(x + 1) - sqrt(x) becomes 1 / (sqrt(x + 1) + sqrt(x)), and log(1 + x) for tiny x is computed with math.log1p(x), exp(x) - 1 with math.expm1(x).

Dangerous form Stable replacement
1 - cos(x) for small x 2 * sin(x / 2)**2
sqrt(x + 1) - sqrt(x) for large x 1 / (sqrt(x + 1) + sqrt(x))
log(1 + x) for small x math.log1p(x)
exp(x) - 1 for small x math.expm1(x)
(a - b)(a + b) vs a² - b² prefer (a - b)(a + b) when a ≈ b

Summation order and accumulated error

Adding many numbers accumulates one rounding error per addition. Adding a tiny number to a huge running total can lose the tiny number entirely.

Python Summation order matters

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The naive loop loses all million ones because each 1e16 + 1 rounds back to 1e16 (the gap near 1e16 is 2). Adding small numbers first, or using math.fsum (which tracks the lost low-order bits) fixes it. NumPy's np.sum uses pairwise summation, which keeps the error growth much smaller than a simple loop.

Kahan compensated summation

You can build an accurate sum yourself by remembering the rounding error and feeding it back in:

Python
def kahan_sum(values):
    total = 0.0
    carry = 0.0                  # the part that was lost
    for v in values:
        y = v - carry
        t = total + y
        carry = (t - total) - y  # what rounding dropped
        total = t
    return total

The error of this sum is nearly independent of the number of terms, instead of growing with it. Use math.fsum in real code; the Kahan loop is worth knowing as an idea.

Other places where digits vanish

  • Absorption. big + tiny returns big. This is why 1e16 + 1 == 1e16.
  • Difference of squares. Computing variance as mean(x²) - mean(x)² can cancel catastrophically; use the two-pass formula or Welford's algorithm.
  • Subtracting from a rounded result. Anything of the form (a + b) - a may not return b.

Whenever a formula subtracts two quantities that are close in the region you care about, stop and look for an algebraic rewrite, a Taylor series for small arguments, or a library function like log1p.

Forward and backward error

Two ways to judge an algorithm are worth knowing. The forward error compares the computed answer with the true answer. The backward error asks a different question: for which slightly changed input would the computed answer be exactly correct? An algorithm is called backward stable when it always returns the exact answer to a problem that differs from the original only by rounding-sized changes in the input. Backward stable algorithms give the best accuracy that the problem's sensitivity allows. The next lessons build on this: whether a result is accurate depends both on the algorithm and on how sensitive the problem is.

Check your understanding

Quick check · 5 questions

of 5 answered You scored / 5 · perfect!

  1. 1. What is catastrophic cancellation?

    The leading digits cancel and what remains is mostly rounding noise from the inputs.
  2. 2. Which rewrite avoids cancellation in 1 - cos(x) for small x?

    The identity 1 - cos x = 2 sin^2(x/2) involves no subtraction of nearly equal numbers.
  3. 3. Why does the naive loop lose the million ones when summing [1e16, 1.0, 1.0, ...]?

    Absorption: adding a number smaller than half the spacing leaves the large total unchanged.
  4. 4. Which function computes log(1 + x) accurately for tiny x?

    log1p avoids forming 1 + x, which would discard the low-order digits of x.
  5. 5. What does it mean for an algorithm to be backward stable?

    The computed result is the exact solution of a nearby problem, with perturbation of the size of rounding errors.

Summary

  • Subtracting nearly equal numbers destroys leading digits (catastrophic cancellation).
  • Fix it by rewriting the formula (identities, conjugates, log1p, expm1) rather than by using more digits.
  • The stable quadratic solver computes the larger root first and gets the other from c / (a r1).
  • Summation order matters; use math.fsum, pairwise sums or Kahan summation.
  • Backward stable algorithms are as accurate as the problem permits.

Next: Truncation Error and Taylor Series