Catastrophic Cancellation
Subtract two numbers that are nearly equal and the leading digits agree and vanish, leaving the digits behind them in charge. The usual telling blames the subtraction. It is the one step here that cannot be blamed: if the two are within a factor of two of each other, their difference is itself a double and the machine returns it exactly. What the subtraction does is uncover an error that was already in the operands, and move it to the front where it can be seen.
New to floating point? Start here
A computer stores a fraction as a handful of binary digits and a scale, and most decimals do not fit. What is stored for 0.1 is not 0.1, and never was. Floating Point is where that happens; this page starts after it.
Every operation then rounds its answer to the nearest storable number, so each one can be off by up to half a step. A unit in the last place is that step, and it is the unit this page measures error in. Epsilon is the same idea as a fraction: the most one rounding can move an answer, relative to its size.
Both of those are small, and both are usually harmless, because an error of half a step in the sixteenth digit stays in the sixteenth digit. This page is about the one operation that moves it to the front.
Numbers in a fixed-size box
A number on paper can be as long as it needs to be. A number in a computer gets a fixed number of digits and no more, so there is always a largest one it can hold and always a smallest difference it can tell apart.
Almost everything surprising about computer arithmetic follows from that. What happens when you count past the largest value depends on which kind of number it is: a fixed-width integer wraps round to the smallest, and a floating-point number goes to infinity instead. A value too fine for the gap is not rejected, it is rounded to the nearest one that fits, and then the rounding is added to the next rounding. These are not faults in the machines here. They are the edges of the box, and the machines are what people built to live inside it.
The machine for this idea on its own is Two's Complement, if you would rather press it than read about it.
Machines here that come first: Floating Point, Two's Complement.
The subtraction that cannot be wrong, and the answer that is
1 Two close numbers subtracted, and the error the subtraction did not make
Start with the step everyone blames. Two numbers, close together, subtracted. Pick any two you like.
- their ratio
- 1.0000
- what the machine returns
- 2.2204460492503131e-16
- and it is the exact difference of the two stored doubles
- exactly, with no error at all
These two are within a factor of two of each other, so their difference is itself a double and the machine returns it exactly. Nothing is lost here. For two finite numbers this close, subtraction is the one operation on this page that cannot lose anything: what it returns is their exact difference as stored. Anything wrong with that answer came in with the operands.
Goldberg says it in one line, about a case where the answer was ruined: “The subtraction did not introduce any error, but rather exposed the error introduced in the earlier multiplications.” He separates the two cases by name. “Catastrophic cancellation occurs when the operands are subject to rounding errors.” “Benign cancellation occurs when subtracting exactly known quantities.” The subtraction is the same operation in both.
2 The same subtraction with operands that were rounded first
So make the operands dirty first. Goldberg works this in base ten with three significant digits, which is small enough to follow and is reproduced here exactly rather than described: “consider b = 3.34, a = 1.22, and c = 2.28”.
- b squared minus 4ac, exactly
- 0.0292
- b squared, rounded to three digits
- 11.2
- 4ac, rounded to three digits
- 11.1
- their difference, which is exact
- 0.1
- units in the last place from the truth
- 70.8
Both operands were correctly rounded before the subtraction touched them, and the subtraction is exact. The answer is still 70.8 units in the last place from the truth. The paper prints 70; it is 70.8, and rounding a figure about rounding is worth showing. The answer has no correct digits at all.
Both operands are correctly rounded. The subtraction is exact. The answer is wrong anyway, and the reason is that the two operands agreed in their leading digits and disagreed in the digits that had already been thrown away. Goldberg's estimate of how bad this gets: “rounding error can contaminate up to half the digits in the roots computed with the quadratic formula”.
3 The formula rearranged so the subtraction never happens
“A formula that exhibits catastrophic cancellation can sometimes be rearranged to eliminate the problem.” Multiply the root by the conjugate over itself and the subtraction is gone. Same algebra, same coefficients, same machine, and now in the arithmetic this browser actually has.
| formula | result | error |
|---|---|---|
| as written (−b + √(b² − 4)) ÷ 2 | -7.4505806e-9 | 25.5 per cent |
| times the conjugate −2 ÷ (b + √(b² − 4)) | -1e-8 | 0.71 epsilon |
| the true root | -1e-8 | — |
Same coefficients, same machine, same rounding on every operation. The rearranged form multiplies top and bottom by the conjugate so the subtraction never happens, and there is then nothing for it to expose.
The true root is not measured against a longer float. Every double is exactly a fraction with a power of two underneath, so the exact value of the expression is a rational this page holds in whole numbers, and the square root is taken to two hundred and forty bits and carried as an interval. The error is a fact rather than an estimate.
4 A formula that is harder to rearrange, and the calculator its author used
Some formulas are harder to rearrange, and the area of a triangle is the one Goldberg spends a theorem on. Heron's formula is two thousand years old and subtracts the longest side from the half-perimeter, which for a thin triangle is exactly the ruinous case. Kahan’s rearrangement is the same area written differently, and it still subtracts: it takes the difference of the two longest sides and then takes that away from the shortest. What it never does is subtract the half-perimeter from a side of nearly the same size, and the distances measured below are what that is worth.
running at 3 significant digits on sides 9.0, 4.53, 4.53 (stored as 9, 4.53, 4.53)
| formula | area, and how far out |
|---|---|
| Heron √(s(s−a)(s−b)(s−c)), s = (a+b+c) ÷ 2 | 3.04 (69.78 out) |
| rearranged a ≥ b ≥ c, then √((a+(b+c))(c−(a−b))(c+(a−b))(a+(b−c))) ÷ 4 | 2.35 (0.78 out) |
| the true area | 2.3422 |
These sides do not fit in 3 significant digits, so the machine holds 9, 4.53, 4.53 and every number below is about that triangle. Two sides that differ by less than a rounding step become the same side. Heron's formula is 69.78 units out and the rearranged one is 0.78. The two are the same area written two ways, and Heron's is the one whose subtraction of the longest side from the half-perimeter can cancel.
Goldberg proves a bound for the rearranged form: “The rounding error incurred when using (7) to compute the area of a triangle is at most 11” times the machine epsilon, “provided that subtraction is performed with a guard digit” and two other conditions. Heron's formula has no such bound, and on the equilateral triangle above it is the rearrangement that is a unit out. Rearranging is not better everywhere.
These ran in this browser when the page loaded. Each claim, whether it held, and the number behind it.
| claim | held | measured |
|---|---|---|
| subtracting two doubles within a factor of two of each other is exact: 2000 pairs, 0 with any error at all | yes | the difference is itself a double, so nothing is lost in the subtraction. Whatever went wrong went wrong before it |
| Goldberg's b squared minus 4ac: exactly 0.0292, computed as 0.1, 70.8 units in the last place out | yes | his paper prints 70; it is 70.8, and both operands were correctly rounded before the subtraction touched them |
| his triangle at three digits: s is 9.05, Heron gives 3.04 and the rearranged formula 2.35 against a true area of 2.34216 | yes | every figure the paper prints. Its 70 ulps is 69.78, its 1 ulp is 0.78, and its 0.7 epsilon is 0.669 |
| the same triangle in this browser: Heron is 79.1 units out and the rearrangement is 0.05 | yes | binary64 has fifty-three bits where Goldberg had three digits, and the shape of the failure is identical |
| on an equilateral triangle at ten digits, Heron gives 43.30127019 and the rearrangement 43.3012702, against a true 43.3012701892 | yes | Kahan's own table 1 prints both. Here the rearranged formula is 1.08 units out and Heron is 0.08: rearranging is not better everywhere |
| Kahan's third row, a triangle 100000 by 99999.99979 by 0.00029: he prints the accurate area as 9.999999990 and this gives 9.99999999 | yes | his own table, at his own precision. The Heron column beside it was computed on an HP-15C and is not reproduced here |
| over 10 quadratics the naive root is wrong by up to 100 per cent and the rearranged one by 1.0 epsilon | yes | same coefficients, same rounding, same machine. The rearranged form never subtracts two close numbers, so there is nothing to expose |
| over 56 needle triangles the rearranged formula never leaves Goldberg's bound of eleven epsilon, and Heron leaves it 28 times | yes | theorem 3 in the 1991 paper, which is a relative-error bound and not a count of units in the last place |
| x squared minus y squared against (x minus y) times (x plus y): 60 of 60 cases are more accurate factored and 0 are worse | yes | the factored form still subtracts, but it subtracts two numbers that carry no rounding error, which is the benign kind |
| over 56 triangles the worst error is 1.55 epsilon with the parentheses and 2.58 without them | yes | the same algebra evaluated in a different order. Kahan writes not to remove them, and this is the measurement behind it |
| over the 360 ways these triangles' sides can arrive, the worst error is 1.57 epsilon with the sort and 2.05 without it | yes | the differences inside the formula change sign when the sides come in another order, so renaming them is part of the formula and not tidiness |
What is real here, and what is not
The blurb this page was commissioned under is wrong
It said that subtracting two close numbers throws away the digits you still needed. It does not throw away anything. If two doubles are within a factor of two of each other their difference is itself a double, so the subtraction is exact and returns the true answer — which is what the first panel sweeps two thousand pairs to show. Kahan is blunter than Goldberg about it: cancellation, he writes, is “at worst the Bearer of Bad Tidings, namely that prior rounding errors discarded digits whose absence now is regretted”. The roster entry was rewritten rather than the page written around it.
The exact values are exact, and the square roots are intervals
Every finite double is a fraction with a power of two underneath, so a sum or product of doubles has an exact rational value that this page holds in whole numbers. A square root usually does not: it is irrational unless the fraction is a perfect square over a perfect square, and a page that printed a rational and called it the truth would be doing the thing it accuses the naive formula of. So a root that is rational is taken exactly, and every other one is computed as an interval two hundred and forty bits wide, with every number derived from it worked out at both ends. Where the two ends print differently, the page says so rather than picking one. An earlier version of these readouts took the lower end alone; the ledger said both, and the ledger was ahead of the code.
Where the paper's own figures are rounded, both numbers are printed
Goldberg reports the discriminant as 70 ulps out; it is 70.8. He reports Heron's area as 70 ulps out; it is 69.78. He reports his own formula as 1 ulp in error; it is 0.78, and as a relative error of 0.7 epsilon; it is 0.669. Every one of those reproduces, and every one is rounded in the paper. Saying “matches” and printing his figure would be this studio's own kind of lie, so both are on the page.
Eleven epsilon is Goldberg's bound and it is not eleven ulps
Theorem 3 of the 1991 paper bounds the relative error of the rearranged area at eleven machine epsilons, under three stated conditions: subtraction with a guard digit, epsilon at most .005, and square roots to within half a unit in the last place. It is a relative-error bound, not a count of units in the last place, and the two units differ by up to the base. Kahan's own manuscript proves no such number; it argues qualitatively that each factor is accurate to a unit or two. The formula is his and the bound is Goldberg's.
Two arithmetics, on purpose
Some panels run in base ten with three significant digits, because that is what Goldberg's worked examples use and it is the only way to reproduce his printed figures rather than approach them. Others run in the binary64 this browser has. The failure has the same shape in both, which is the point of showing both, and every panel says which arithmetic it is in. The decimal calculator rounds every intermediate result the way such a machine would, including the square root.
Kahan's table cannot be reproduced column for column, and this page does not try
His table of needle-like triangles was computed on an HP-15C carrying ten significant decimal digits, and its Heron column is what that calculator did rather than what correctly rounded ten-digit arithmetic does. The accurate column IS a claim about the true area and is checkable: for the triangle 100000 by 99999.99979 by 0.00029 he prints 9.999999990 and this page's rearranged formula at ten digits gives the same. His Heron column is left alone.
Kahan's own papers are read from the Internet Archive, and that is not a preference
Both were fetched from people.eecs.berkeley.edu earlier the same day this page was built. By the afternoon that host was redirecting to a different machine and answering 404 for both files. The copies cited here are the Internet Archive's, captured in January 2024, byte for byte the size of the originals that were fetched in the morning — and one of them still carries a page header pointing at a Berkeley hostname that has not existed for years. A page whose citation stops resolving is a page nobody can check.
Nobody here knows who coined the phrase
Goldberg 1991 is the earliest document this page holds a copy of that names and defines both catastrophic and benign cancellation. Searching for an earlier use turned up Wilkinson 1963 and Sterbenz 1974 as the era's foundational texts and no fetchable evidence that either uses the phrase; Goldberg's own bibliography cites a 1972 Kahan survey that is not fetchable either. So the page says what it looked for and did not find, rather than naming somebody.
What this page leaves to Floating Point
How a decimal becomes a double, what the exact stored value of 0.1 is, where the counting stops, and why 0.1 plus 0.2 is not 0.3 are all Floating Point, and none of it is re-derived here. That page is about the error in a stored value. This one is about the error in a computation, and it is a different subject: every number in the second panel was stored perfectly well.
The copy read is Oracle's reprint, not the ACM original
The archived text says so itself: it is an edited reprint of the March 1991 Computing Surveys paper, and its section numbering and figure labels are the manual's rather than the journal's. The DOI is cited beside it as the citation of record; it answers with a sign-in page rather than the paper, so it is recorded as unfetchable and was not read. Both facts are on the page because a reader checking a quotation needs to know which document to open.
Sound: no
Asked and answered so it does not get re-opened. There is nothing here with a duration. The measurement is a count of units in the last place, and a tone whose pitch stood for an error would be a decoration of a number that is already on the screen.
Sources
- David Goldberg, What Every Computer Scientist Should Know About Floating-Point Arithmetic, ACM Computing Surveys 23(1), March 1991, in Oracle's edited reprint. Both kinds of cancellation are named and defined here, and every worked figure on this page is reproduced from it.
- The same paper at its DOI, which is the citation of record. It answers with a sign-in page rather than the paper, so it is not the copy this page was written from.
- W. Kahan, Miscalculating Area and Angles of a Needle-like Triangle, the September 2014 revision, stamped work in progress and served as ten pages of a twenty-three page document. The rearranged formula, the instruction not to remove its parentheses, and the table of triangles this page checks itself against. Read from the Internet Archive's copy, because Berkeley's own host answered 404 on 2026-09-10.
- W. Kahan, How Futile are Mindless Assessments of Roundoff in Floating-Point Computation?, 2006. Section 10 is titled Cancellation is Not the Culprit, and section 6 is where cancellation is called the Bearer of Bad Tidings. Also from the Internet Archive, for the same reason.
- Logical Art, the studio this belongs to.