Catastrophic cancellation¶

Level: 301 · deep dive

One line: Subtracting two nearly equal numbers can destroy almost every significant figure at once, silently, leaving an answer that still looks precise — and it is the point where measurement error and machine error stop being two subjects.

The one operation that breaks the rules¶

Every other operation in this chapter loses a digit or two. Subtraction can take ten and give back one.

Two measurements, each good to five significant figures — four-thousandths of a percent, laboratory-grade:

A = 1.2345  ±0.00005      0.0041% relative
B = 1.2344  ±0.00005      0.0041% relative

Subtract them. The difference is 0.0001, and its uncertainty is √2 × 0.00005 = 0.00007:

A − B = 0.0001 ± 0.00007        71% relative

Ten significant figures went in. About one came out. The relative error was amplified roughly seventeen thousand times, and the two measurements were consistent with a difference of zero.

Nothing was done wrong. No rule was broken, no rounding was sloppy. The information was simply never there: the quantity being computed is smaller than the noise in the inputs, and subtraction is the operation that reveals it.

What the program prints¶

Verified output of catastrophic_cancellation.py — regenerated by tools/run_examples.py, never hand-typed.

1. ON PAPER, WITH NO COMPUTER INVOLVED
     A = 1.2345   5 s.f.   +/- 0.00005   = 0.0041% relative
     B = 1.2344   5 s.f.   +/- 0.00005   = 0.0041% relative
     A - B = 0.0001                        1 s.f.
     uncertainty +/- 0.0000707  =  71% relative
     Ten significant figures went in. About one came out.
     Relative error was amplified 17,458x.

     Nothing was done wrong. The information simply was not there:
     both measurements were consistent with a difference of zero.

2. THE SAME THING TO A COMPUTER
   Cancellation does not CREATE error. It removes the large leading
   digits that were hiding error already there.
     0.1 + 0.2 is stored as  0.3000000000000000444089209850062616169452667236328125
     0.3       is stored as  0.299999999999999988897769753748434595763683319091796875
     the sum is wrong by     4.441E-17
     which is                1.480E-14 %  -- invisible

   Now subtract. The true answer is exactly zero:
     (0.1 + 0.2) - 0.3  =  5.551115123125783e-17
     The absolute error did not change. The 0.3 that was masking it
     is gone, so a rounding artifact is now 100% of the answer.

3. THE CLASSIC: THE QUADRATIC FORMULA
   x^2 + bx + c = 0, with b enormous and c small.
     b = 1e+08   c = 1
     sqrt(b^2 - 4c) = 99999999.99999999
       ...which is b itself to every digit a float can hold.

     naive   (-b + sqrt(b^2-4c)) / 2   = -7.450580596923828e-09
     stable  -2c / (b + sqrt(b^2-4c))  = -1e-08
     exact   (50-digit arithmetic)     = -1.00000000000000010e-8

     naive  is off by  25.4942%
     stable is off by   0.0000%
     Same formula, same inputs, same hardware. One subtraction moved.

4. CONDITIONING vs STABILITY -- two different faults
   ill-CONDITIONED problem : small input change -> large output change.
                             The problem's fault. No algorithm escapes it.
   un-STABLE algorithm     : the problem is fine; this route through it
                             is not. Section 3 is this kind, and the fix
                             was free.
   Section 1 is the first kind: no cleverness recovers digits that were
   never measured. Knowing which one you have is the whole skill.

5. THE PRACTICAL RULE
   Whenever you subtract two quantities that are close, stop and ask
   what the difference is RELATIVE to its own uncertainty. If the
   answer is 'not much', the digits on your screen are decoration.

Cancellation exposes error; it does not create it¶

Section 2 above is the sentence worth taking away, and it is the one usually got backwards.

0.1 + 0.2 in binary floating point comes out as 0.3000000000000000444…. The error — about 4.4 × 10⁻¹⁷ — is buried in the seventeenth digit, and as a share of 0.3 it is 1.5 × 10⁻¹⁴ percent. Utterly invisible; you could ship it for years.

Why 0.1 was wrong before you did anything to it. This page takes for granted that 0.1 is not 0.1, and never explains it. The reason is that a fraction survives in binary only when its denominator is a power of two — 1/2, 1/4, 3/4 are exact; 1/10 and 1/5 repeat forever and get cut off. That is a lesson of its own, and the sibling Rust library already has a thorough one: What a float actually stores ↗. It is a Rust page, but the IEEE 754 mechanics it walks through — the repeating binary expansion, the 24- and 53-bit cuts, and the fact that the discarded tail rounds rather than truncates, so errors go in both directions — are the same on every machine and in every language.

Read that one for where the error comes from; this one is what happens to it next.

Now subtract 0.3. The true answer is exactly zero. The computed answer is 5.551115123125783e-17.

The absolute error did not change. It was 4.4 × 10⁻¹⁷ before the subtraction and it is about that after. What changed is that the 0.3 which had been masking it is gone, so a rounding artifact is promoted from the seventeenth digit to the only digit. That is the whole mechanism, in measurement and in binary alike: cancellation removes the large leading digits that were hiding the error you already had.

Which is also why if (a - b) == 0 and if a == b are not the same test, and why neither is the test you want.

The quadratic formula, and a free fix¶

Section 3 is the classic, and it is worth reading closely because it separates two things that get conflated.

Solve x² + bx + c = 0 with b = 10⁸ and c = 1. The small root is about −10⁻⁸. The textbook formula computes it as (−b + √(b² − 4c)) / 2 — and √(b² − 4c) equals b to every digit a float can hold, so the numerator is a catastrophic cancellation. The result is wrong by 25%.

Multiply through by the conjugate and the same root becomes −2c / (b + √(b² − 4c)). Now it is an addition of two positive quantities. No cancellation, and the answer is correct to full precision.

Same formula. Same inputs. Same hardware. One subtraction moved, and 25% error became none.

Two different faults, and telling them apart¶

This is the skill the page is really about:

An ill-conditioned problem — a small change in the input causes a large change in the output. This is the problem's fault. No algorithm escapes it, and no amount of precision rescues it, because the sensitivity is a property of the question, not the method. The two measurements in the opening section are this kind. Their difference is genuinely unknown, and cleverness cannot recover digits that were never measured.

An unstable algorithm — the problem is perfectly well-behaved; this particular route through it is not. The quadratic formula is this kind, and the fix cost nothing.

Confusing them wastes effort in both directions: you can spend a week hardening an algorithm against an ill-conditioned problem that will defeat any algorithm, or accept a garbage answer as "inherent" when a two-line rearrangement would have fixed it. The diagnostic question is whether an independent method gets a materially different answer. If yes, your algorithm is unstable. If every method agrees on garbage, the problem is ill-conditioned and the honest output is a wide interval.

The practical rule¶

Whenever you subtract two quantities that are close, stop and ask what the difference is relative to its own uncertainty. If the answer is "not much", the digits on your screen are decoration.

Where this shows up in real code: differences of large timestamps, variance = E[x²] − E[x]² (use a two-pass or Welford algorithm instead), finite-difference derivatives with too small a step, subtracting cumulative totals, and any before/after comparison of two large near-equal aggregates.

Run it yourself¶

From the root of your clone of this repository:

python3 01_Precision/catastrophic_cancellation/examples/catastrophic_cancellation.py