Catastrophic cancellation
A Socratic walk-through of catastrophic cancellation — reasoned out one step at a time, not lectured.
The question we started with
THE QUESTION #Why can subtracting two highly accurate numbers leave an answer with no correct digits at all?
Two quantities are each known to eight correct significant digits — an accuracy most measurements never approach. Subtract one from the other and the answer can be wrong in its very first digit.
The obvious suspect is the subtraction. But subtraction is the operation a machine performs most exactly of all, and in the case that hurts most it is provably exact: nothing is rounded, nothing is dropped. So if the subtraction is blameless and the inputs were excellent, where is there left for the error to come from?
Reasoning it through
REASONING #Work in eight-significant-digit decimal, so every step can be checked by hand.
Let the true values be a = 1.23456789 and b = 1.23456781. Stored to eight digits they become 1.2345679 and 1.2345678 — the first rounded up, the second down, each off by 1 × 10⁻⁸. Relative to numbers of size about 1.23, that is an error of roughly 8 × 10⁻⁹: excellent, and about as good as the format allows.
Now subtract. The machine computes 1.2345679 − 1.2345678 = 1.0 × 10⁻⁷, and it computes it exactly — the answer is representable with digits to spare. The true difference is 1.23456789 − 1.23456781 = 8.0 × 10⁻⁸.
Compare them. Computed 1.0 × 10⁻⁷ against a truth of 8.0 × 10⁻⁸: not one correct significant digit. And yet look at the absolute error: 1.0 × 10⁻⁷ − 8.0 × 10⁻⁸ = 2 × 10⁻⁸, which is exactly the sum of the two input errors, 1 × 10⁻⁸ each. The subtraction added nothing whatsoever.
So the error did not grow. The yardstick shrank. Before the operation, an error of 2 × 10⁻⁸ was being measured against numbers of size 1.23 and was negligible. Afterwards the same error is measured against 8 × 10⁻⁸ and is a quarter of it. Nothing was destroyed; a fixed quantity of pre-existing error was simply promoted from the last digit to the first.
Put a number on the promotion. The relative error went from about 8 × 10⁻⁹ to 0.25, an amplification of about 3.1 × 10⁷. Where does that factor come from? Take the ratio (|a| + |b|) / |a − b| = 2.4691357 / (8 × 10⁻⁸) ≈ 3.09 × 10⁷ — the same number. That is the condition number of subtraction, and it says the amplification is governed by one thing only: how close the two operands are relative to their size.
Which yields a rule you can apply by eye. If two numbers agree in their leading k significant digits, those k digits cancel to zero and play no part in the answer; what remains is built from the digits after them. Start with p correct digits and you finish with at most p − k. Our operands agreed in seven digits out of eight, so at most one should have survived — and in fact none did, because the two roundings happened to go in opposite directions and consumed the last one too.
The analogy
THE ANALOGY #Imagine measuring the thickness of a sheet of paper by measuring a stack of books, then the same stack with the sheet on top, and subtracting. Each height is measured superbly — to a tenth of a millimetre on a metre of books, one part in ten thousand. The sheet is a tenth of a millimetre thick. The subtraction is done perfectly and the answer is nonsense, because the tiny quantity you wanted is the same size as the uncertainty you were carrying all along and never noticed.
the paper case suggests the fix is a better ruler, whereas here more precision only postpones the failure — it does not remove the amplification, and the standard repair is not a finer instrument at all but a different formula that never forms the difference.
Clarifying the model
THE MODEL #Three corrections, and the first is the one the folklore gets backwards.
The subtraction is not merely blameless, it is exact in the dangerous case. Sterbenz's lemma says that for binary floating-point numbers with b/2 ≤ a ≤ 2b, the difference a − b is representable exactly, so the operation introduces no rounding at all. Catastrophic cancellation is therefore not an example of an unstable algorithm producing new error. It is an ill-conditioned problem: the true answer is hypersensitive to the inputs, and the algorithm is faithfully reporting that sensitivity. Keeping those two ideas apart — conditioning is a property of the problem, stability a property of the method — is most of what numerical analysis asks of you.
Second, this bounds what extra precision buys. Doubling to sixteen digits does not stop the amplification; it just means the surviving digits start further down. If the operands agree to fifteen digits you are in the same position again. Precision moves the cliff; it does not remove it.
Third, and connecting to a neighbouring point: representation error explains why the operands were imperfect in the first place — one tenth has no finite binary expansion, and every decimal you type is rounded on the way in. That story is about error being created at input. This one is about an operation that creates none and merely changes what the existing error is measured against. The two compose, and neither is a version of the other.
Now the test that would refute the account. If the subtraction destroyed information, no rearrangement could recover it. So take √(x + 1) − √x at x = 10⁸ in eight-digit arithmetic. √100000001 is 10000.00005, which stores as 10000.000; √100000000 is 10000.000 exactly; the difference is 0. Total loss. Now rewrite it, multiplying above and below by the sum: √(x+1) − √x = 1 / (√(x+1) + √x) = 1 / 20000.000 = 5.0000000 × 10⁻⁵, against a true value of 4.9999999875 × 10⁻⁵ — correct to eight digits. Same inputs, same precision, no subtraction of near-equals, full accuracy. Since the information was recoverable, the subtraction cannot have destroyed it. Had the rewritten form been equally wrong, this whole explanation would be false.
A picture of it
THE PICTURE #How to readEach bar is one pair of operands, both known to eight correct significant digits, differing only in how much of their leading run of digits is identical. Read across for how similar they are, and down the bar for what survives. At the far left the numbers share nothing and the difference keeps all eight digits — subtracting unlike quantities is entirely safe. Every step to the right cancels one more shared digit and costs exactly one digit of the answer, which is why the fall is straight rather than curved. The rightmost bar is the case in the text: identical to the working precision, nothing correct remaining.
What became clearer
WHAT CLEARED #Catastrophic cancellation destroys no information and adds no error. The absolute error is the same quantity before and after; the subtraction merely deletes the shared leading digits, so an error that was invisible against operands of size one becomes the dominant part of an answer of size 10⁻⁷. The amplification factor is (|a| + |b|) / |a − b|, and the digit version is easier still: however many leading digits the two numbers share, that is how many the answer loses. The repair is never more precision — it is an equivalent formula in which the near-equal quantities never meet.
Where to go next
ONWARD #- Why the standard quadratic formula loses accuracy for one root when 4ac is small, and how choosing the sign of the square root repairs it.
Key terms
TERMS #| Term | What it means |
|---|---|
| Condition number | how much a problem amplifies relative error in its inputs; for a − b it is (|a| + |b|) / |a − b|. |
| Stability | a property of an algorithm: whether it introduces error beyond what the problem's conditioning makes unavoidable. |
| Sterbenz's lemma | the result that a − b is exact in binary floating point whenever a and b lie within a factor of two of each other. |
Every term the collection defines is gathered in the glossary.