Floating point gotchas — catastrophic cancellation, associativity failure: Visual walkthrough

Step 1 — A number line with gaps in it

WHAT. A real number line is smooth: between any two points there is always another point. A computer's number line is not smooth. It can only land on a finite set of dots. Between neighbouring dots there is a gap — an interval with no representable number at all.

WHY. A double has a fixed budget of bits (see IEEE-754 floating point representation). Fixed bits means a finite number of dots. Everything about "lost digits" is really "your true value fell into a gap and got snapped to the nearest dot."

PICTURE. Look at the figure. Near $1.0$ the dots are close together; near $1000$ they are far apart. The spacing is relative — it grows with the size of the number.

Figure — Floating point gotchas — catastrophic cancellation, associativity failure

The single most important word here is relative: the grid is fine for small numbers and coarse for big ones.

Step 2 — Rounding: snapping to the nearest dot

WHAT. When your true value $x$ isn't one of the dots, the computer stores the nearest dot. We call the stored value $fl (x)$ (read "float of $x$ ").

WHY. You cannot store what isn't representable. Nearest-dot rounding is the least-bad choice: the error is at most half a gap, because if you were more than half a gap away, the other dot would be closer.

PICTURE. The red arrow shows the true $x$ ; the violet dot is where it lands. The error is the length of the short segment, and it can never exceed half the gap (the shaded band).

This tool — writing every stored number as true value times $(1 + δ)$ — is the whole reason we can track error algebraically. See Relative vs absolute error for the two flavours.

Step 3 — Two nearly-equal numbers, each carrying a wobble

WHAT. Take two exact numbers $a$ and $b$ that are close in value. The computer holds $\overset{a}{^} = a (1 + δ_{a})$ and $\hat{b} = b (1 + δ_{b})$ .

WHY. We want to subtract them. Before we can, we must be honest: neither input is exact. Each already carries an absolute error $a δ_{a}$ and $b δ_{b}$ . Because $a$ and $b$ are big, these absolute errors are not tiny — they are $\sim u \times (big number)$ .

PICTURE. Two tall bars, $a$ and $b$ , almost the same height. On top of each sits a small "fuzz" band — the absolute error. Notice the fuzz is a fixed fraction of the tall bar, so in absolute terms it is chunky.

Keep your eye on these two chunky fuzz-bands. They are about to survive a subtraction that shrinks the answer to nothing.

Step 4 — The subtraction: the answer shrinks, the fuzz does not

WHAT. Compute $r = a - b$ (true) versus $\overset{r}{^} = \overset{a}{^} - \hat{b}$ (stored). Subtract the two lines.

WHY. This is the moment of the crime. The tall bars cancel down to a tiny sliver $r = a - b$ . But the fuzz-bands do not cancel — they were independent wobbles. So a tiny answer now sits next to fuzz that used to be small relative to $a$ but is huge relative to $r$ .

PICTURE. The two tall bars are drawn overlapping; their difference is the thin sliver at the top. The fuzz from both bars piles onto that sliver — visually the error band is a big fraction of the sliver.

Step 5 — Dividing by a tiny answer: the amplifier appears

WHAT. Ask the honest question: how bad is the relative error of the result? Divide the leftover error by the true result $r = a - b$ .

WHY. Relative error is what tells you how many correct digits remain (see Round-off error propagation). A big absolute error over a big answer is fine; a big absolute error over a tiny answer is a disaster. Division by the tiny $r$ is where the explosion happens.

PICTURE. A see-saw: numerator (fixed-size fuzz $∣ a ∣ + ∣ b ∣$ scale) on one side, denominator $∣ a - b ∣$ shrinking toward zero on the other. As the denominator collapses, the ratio shoots to the sky.

Step 6 — A worked collapse: watch the digits die

WHAT. Put numbers in. Let $a = 200000.00001$ and $b = 200000.0$ , so the true difference is $r = 1 0^{- 5}$ .

WHY. Abstract $\infty$ is unconvincing; a concrete digit count is not. We compute the amplification factor and predict how many digits survive.

PICTURE. The bar chart shows $16$ good digits going in and only a handful coming out, with the lost digits greyed to nothing.

Step 7 — The degenerate cases (never leave a gap)

WHAT. Sweep every boundary of the formula so no scenario surprises you.

WHY. A promise to a smart 12-year-old: you will never hit a case I did not show. Here are all of them.

PICTURE. Four mini-panels, one per case, each with the factor's value written in.

Definition All the edge cases of

$\frac{∣ a ∣ + ∣ b ∣}{∣ a - b ∣}$

$a = b$ exactly (panel 1): denominator $= 0$ , factor $= \infty$ . The true result is $0$ ; every surviving digit can be wrong. This is total cancellation.
$a$ , $b$ far apart (panel 2): e.g. $a = 10$ , $b = 0.001$ . Denominator $\approx$ numerator, factor $\approx 1$ . Subtraction is perfectly safe — no cancellation.
Opposite signs, $a > 0 > b$ (panel 3): now $∣ a - b ∣ = ∣ a ∣ + ∣ b ∣$ , so the factor is exactly $1$ . Subtracting a positive from... wait — this is really an addition of magnitudes, and addition of same-sign magnitudes never cancels. Safe.
One input is $0$ (panel 4): say $b = 0$ . Factor $= ∣ a ∣/∣ a ∣ = 1$ . Nothing to cancel; the result is just $\overset{a}{^}$ , error $\sim u$ . Safe.

The rule: danger requires same sign and nearly equal magnitude. Break either condition and you are safe.

The one-picture summary

This final figure compresses all seven steps: gappy number line → snap-to-dot with fuzz → two tall bars with inherited fuzz → subtraction collapses the bars but keeps the fuzz → division by the sliver → the amplification factor $\frac{∣ a ∣ + ∣ b ∣}{∣ a - b ∣}$ → digits lost.

Recall Feynman retelling — the whole walkthrough in plain words

A computer's number line has gaps, and the gaps get wider for bigger numbers. When you write down a number, it jumps to the nearest allowed dot — that little jump is the error, and it's always about the same tiny fraction of the number.

Now take two big numbers that are almost the same. Each already jumped a little — and because they're big, those little jumps are chunky in real terms. When you subtract the two big numbers, the big parts cancel and you're left with a tiny answer... but the two chunky jumps are still there, sitting on top of a tiny answer. Suddenly the error, which was a small slice of a big number, is a huge slice of a small number.

To measure how bad it got, divide the leftover error by the tiny answer. Dividing by something tiny makes it explode. The exact "explosion factor" is $\frac{∣ a ∣ + ∣ b ∣}{∣ a - b ∣}$ : big things on top, tiny difference on the bottom. In our example that's $4 \times 1 0^{10}$ , which eats about $11$ of your $16$ good digits.

The escape hatch: don't subtract twins. Rewrite the formula so the near-equal subtraction never happens — like $x_{-} = c / (a x_{+})$ for the quadratic, or $1 - cos x = 2 sin^{2} (x /2)$ . The subtraction is never wrong; it just reveals damage that was already baked in. So route around it.

Recall

Recall Cover the answers

Where does the error in $a - b$ actually come from? ::: It's inherited from storing $\overset{a}{^}, \hat{b}$ ; the subtraction is exact (Sterbenz) and only exposes it. What is the amplification factor for subtracting $a$ and $b$ ? ::: $\frac{∣ a ∣ + ∣ b ∣}{∣ a - b ∣}$ . For $a = 200000.00001$ , $b = 200000$ , roughly how many digits are lost? ::: About 11 (the factor is $\approx 4 \times 1 0^{10}$ , and $lo g_{10} (4 \times 1 0^{10}) \approx 10.6$ ). When is subtraction perfectly safe? ::: When the numbers have opposite signs, or very different magnitudes, or one is zero — factor stays near $1$ . Does using float128 cure catastrophic cancellation? ::: No — it lowers $u$ but leaves the amplification factor unchanged; reformulate instead.