Catastrophic Cancellation
Goals
Understand, with a formula, how much catastrophic cancellation amplifies relative error, verify its effects through concrete numerical examples, and learn how to derive safe alternative formulas.
Contents
1. Definition
Catastrophic cancellation occurs when two nearly equal numbers are subtracted (or, equivalently, when two numbers of opposite sign and nearly equal magnitude are added): the leading digits cancel, and the rounding or approximation errors already present in the inputs show up as a large relative error in the difference. The result retains far fewer reliable significant digits.
The Essence of Cancellation
When $x \approx y$, computing $x - y$ causes all matching upper digits to cancel. The remaining lower digits contain rounding errors, so the relative error of the result is dramatically larger than that of the inputs.
Amplification of Relative Error
Let the approximations of the true values $x$, $y$ be $\hat{x} = x(1 + \delta_x)$, $\hat{y} = y(1 + \delta_y)$, and assume the subtraction $\hat{x} - \hat{y}$ itself is exact. Then
$$\left|\frac{(\hat{x} - \hat{y}) - (x - y)}{x - y}\right| = \frac{|x\delta_x - y\delta_y|}{|x - y|} \le \frac{|x| + |y|}{|x - y|} \max(|\delta_x|, |\delta_y|)$$When $x \approx y$, the denominator $|x - y|$ is small and the factor $\dfrac{|x| + |y|}{|x - y|}$ becomes large. The smaller the difference, the more the relative errors of the inputs are amplified (in the example of Section 2 the factor is about $2200$).
Cancellation does not "create" new error; it "reveals" pre-existing rounding errors.
2. Mechanism
Consider 4-digit decimal floating-point arithmetic (digits beyond the fourth are chopped).
$x = 1.234 \times 10^0$ (true value $1.2345678\ldots$)
$y = 1.233 \times 10^0$ (true value $1.2334567\ldots$)
$x - y = 0.001 \times 10^0 = 1.000 \times 10^{-3}$
The true difference is $1.2345678\ldots - 1.2334567\ldots = 0.0011111\ldots$, so the computed result $0.001$ has a relative error of about $10\%$, more than 200 times the relative errors of the inputs ($4.6 \times 10^{-4}$ and $3.7 \times 10^{-4}$). The original $x$ and $y$ had 4 significant digits, but the subtraction result has only 1 reliable digit. After normalization to $1.000 \times 10^{-3}$, the trailing three zeros are "garbage digits" carrying no information.
3. Typical Occurrences
Quadratic Formula
In the solution $x = \dfrac{-b \pm \sqrt{b^2 - 4ac}}{2a}$ of $ax^2 + bx + c = 0$ ($a \ne 0$, $b^2 - 4ac \ge 0$), when $b^2 \gg |4ac|$, we get $\sqrt{b^2 - 4ac} \approx |b|$, and $-b + \sqrt{b^2-4ac}$ (if $b > 0$) or $-b - \sqrt{b^2-4ac}$ (if $b < 0$) suffers from cancellation.
Numerical Differentiation
In the difference formula $f'(x) \approx \dfrac{f(x+h) - f(x)}{h}$, when $h$ is very small, $f(x+h) \approx f(x)$ and the numerator suffers from cancellation. On the other hand, a larger $h$ increases the truncation error, so $h$ has an appropriate size.
Trigonometric Functions
Computing $1 - \cos x$ for $x \approx 0$ causes cancellation since $\cos x \approx 1 - x^2/2$, so $1 - \cos x \approx x^2/2$ is very small.
Exponential Functions
Computing $e^x - 1$ for $x \approx 0$ causes cancellation since $e^x \approx 1$. Most languages provide expm1(x) for accurate evaluation of $e^x - 1$, and log1p(x) for $\log(1+x)$.
4. Avoidance Techniques
Rationalization
For $x \ge 0$, and especially for large $x$, $\sqrt{x+1}$ and $\sqrt{x}$ are nearly equal, so $\sqrt{x+1} - \sqrt{x}$ suffers from cancellation. To avoid it, rationalize the numerator:
$$\sqrt{x+1} - \sqrt{x} = \dfrac{(\sqrt{x+1} - \sqrt{x})(\sqrt{x+1} + \sqrt{x})}{\sqrt{x+1} + \sqrt{x}} = \dfrac{1}{\sqrt{x+1} + \sqrt{x}}$$The right-hand side has no subtraction and is free of cancellation.
Taylor Expansion
Instead of computing $1 - \cos x$ for $x \approx 0$, use:
$$1 - \cos x = \dfrac{x^2}{2} - \dfrac{x^4}{24} + \cdots \approx \dfrac{x^2}{2}$$This is an approximation for sufficiently small $x$; the truncated term $x^4/24$ is the error (a relative error of about $x^2/12$).
Algebraic Identities
For the quadratic formula ($b \ne 0$), the root that adds terms of the same sign as $-b$, $x_1 = \dfrac{-b - \operatorname{sgn}(b)\sqrt{b^2 - 4ac}}{2a}$, does not suffer from cancellation, so compute it first; then, if $x_1 \ne 0$, use Vieta's formula $x_1 x_2 = c/a$ to get $x_2 = \dfrac{c}{a x_1}$.
Half-Angle Identity
Rewriting with the half-angle identity $1 - \cos x = 2\sin^2(x/2)$ avoids the direct subtraction of $1$ and $\cos x$. Unlike the Taylor expansion, this is an identity, so it works for any size of $x$.
5. Comparison with Absorption
In English, “loss of significance” is often used as a synonym for catastrophic cancellation. The phenomenon called 情報落ち in Japanese—the lower digits of the smaller operand being lost when numbers of very different magnitudes are added—is usually called absorption (or swamping). Chapter 10 of this series is titled “Loss of Significance (Absorption)”; on this page we call it absorption.
| Property | Catastrophic Cancellation | Absorption |
|---|---|---|
| Cause | Subtraction of nearly equal values | Addition/subtraction of values with very different magnitudes |
| What is lost | Upper significant digits | Lower digits of the smaller value |
| Operation | Effective subtraction (subtracting numbers of the same sign, adding numbers of opposite sign) | Occurs in both addition and subtraction |
| Result | Increased relative error | Disappearance of small value's information |
| Avoidance | Expression reformulation, expansion | Reordering operations, compensated summation |
6. Worked Example
Example: Quadratic $x^2 - 10^8 x + 1 = 0$
The discriminant is $b^2 - 4ac = 10^{16} - 4 \approx 10^{16}$, so $\sqrt{b^2 - 4ac} \approx 10^8$.
Unstable computation: $x_2 = \dfrac{10^8 - \sqrt{10^{16} - 4}}{2}$ suffers severe cancellation.
Stable computation: First compute $x_1 = \dfrac{10^8 + \sqrt{10^{16} - 4}}{2} \approx 10^8$, then use Vieta's formula $x_2 = 1/x_1 \approx 10^{-8}$.
Computed in double precision, the unstable formula gives $x_2 = 7.450580596923828 \times 10^{-9}$ (a relative error of about $25\%$), while the stable one gives $x_2 = 1.0 \times 10^{-8}$ (a relative error below $10^{-16}$). The true value is $1.0000000000000001\ldots \times 10^{-8}$.
7. FAQ
Q1. What is catastrophic cancellation?
It is the phenomenon in which, when two nearly equal numbers are subtracted (or two numbers of opposite sign and nearly equal magnitude are added), the leading digits cancel and the rounding or approximation errors already present in the inputs show up as a large relative error in the difference.
Q2. How does catastrophic cancellation differ from absorption?
In catastrophic cancellation, the leading digits cancel in an effective subtraction of nearly equal values (subtracting numbers of the same sign or adding numbers of opposite sign), and the relative error is amplified. In absorption, the lower digits of the smaller value are lost when adding or subtracting values of very different magnitudes. (In English, “loss of significance” usually means catastrophic cancellation.)
Q3. How can catastrophic cancellation be avoided?
The main techniques are (1) identity transformations such as rationalization that avoid directly subtracting nearly equal numbers, (2) Taylor expansion approximations (used only for sufficiently small $x$), (3) algebraic identities such as Vieta's formulas, and (4) higher-precision arithmetic. Note that (4) only postpones the cancellation; the instability of the formula itself remains.
8. References
- Wikipedia "Catastrophic cancellation"
- D. Goldberg, "What Every Computer Scientist Should Know About Floating-Point Arithmetic," ACM Computing Surveys, vol. 23, no. 1, pp. 5--48, 1991.
- N. J. Higham, Accuracy and Stability of Numerical Algorithms, 2nd ed., SIAM, 2002.