Catastrophic cancellation
Catastrophic cancellation is the severe loss of numerical significance that occurs when nearly equal quantities are subtracted in finite-precision arithmetic. The subtraction removes leading digits shared by both operands, leaving a result whose remaining digits are dominated by approximation errors already present in the operands. Although the arithmetic operation may be performed exactly, the relative error of the result can be much larger than the relative errors of the quantities from which it was formed.
The phenomenon is a central distinction between the mathematical evaluation of an expression and its numerical evaluation. Algebraically equivalent formulas can exhibit substantially different behavior when their intermediate quantities are rounded. Catastrophic cancellation therefore concerns the interaction among rounding error, the conditioning of a problem, and the stability of the algorithm used to evaluate it.
Error amplification
Let the exact operands be (x) and (y), while their stored approximations are
[ \widehat{x}=x(1+\delta_x), \qquad \widehat{y}=y(1+\delta_y), ]
where (\delta_x) and (\delta_y) denote small relative errors. Ignoring the rounding of the subtraction itself, the computed difference is
[ \widehat{x}-\widehat{y} =(x-y)+x\delta_x-y\delta_y. ]
Its relative error with respect to the exact difference is therefore approximately
[ \frac{x\delta_x-y\delta_y}{x-y}. ]
When (x) and (y) are close, the denominator is small even though the error terms in the numerator remain proportional to the much larger operands. The subtraction consequently magnifies their inherited errors. If (x-y) is several orders of magnitude smaller than either operand, a corresponding number of significant digits can disappear from the result.
For example, suppose that decimal arithmetic stores six significant digits and forms
[ x=1.23457,\qquad y=1.23456. ]
The computed difference is
[ x-y=0.00001. ]
The displayed result contains only one nonzero significant digit. Small errors in the last retained digits of (x) and (y) can therefore produce a relative error in the difference that is large, even though each operand individually appears accurate to six significant digits.
Cancellation is not synonymous with subtraction. If the operands are exact and their difference is represented exactly, the disappearance of common leading digits does not itself introduce an error. In binary floating-point arithmetic, the Sterbenz lemma states that the subtraction of two floating-point numbers is exact when the numbers are sufficiently close and satisfy certain range conditions. Catastrophic behavior arises because exact subtraction can expose errors introduced during the earlier computation or representation of those operands.
Conditioning and algorithmic stability
The sensitivity of subtraction is partly an intrinsic property of the underlying problem. For the function
[ f(x,y)=x-y, ]
a componentwise relative condition number is proportional to
[ \frac{|x|+|y|}{|x-y|}. ]
This quantity becomes large when the operands are nearly equal. If the available data contain independent uncertainty, no algebraic reformulation can recover information absent from those data.
A different situation occurs when the operands are highly correlated because both were generated from the same mathematical variable. An expression may then be well-conditioned as a whole despite containing an unstable intermediate subtraction. Algebraic transformation can remove the unstable intermediate operation without changing the underlying function. This distinction separates poor conditioning, which belongs to the mathematical problem, from numerical instability, which belongs to a particular computational method.
The severity of cancellation also depends on what follows the subtraction. A small absolute error may remain inconsequential when the result contributes only a small additive correction. The same error can dominate a later division, logarithm, or normalization if the cancelled quantity appears in a denominator or establishes the scale of subsequent calculations.
Algebraically equivalent forms
A standard example occurs in the evaluation of
[ f(x)=\sqrt{x+1}-\sqrt{x} ]
for large positive (x). Both square roots are approximately (\sqrt{x}), while their difference is much smaller. Rationalization gives the equivalent expression
[ f(x)=\frac{1}{\sqrt{x+1}+\sqrt{x}}. ]
The second form avoids the subtraction of nearly equal quantities. Its intermediate values remain on scales comparable to those of the final reciprocal, so rounding in the square-root evaluations is not amplified by cancellation.
A similar effect appears for small (x) in
[ 1-\cos x. ]
Because (\cos x) approaches (1) quadratically, direct evaluation subtracts nearly equal numbers. The identity
[ 1-\cos x=2\sin^2\left(\frac{x}{2}\right) ]
expresses the same function without forming that difference. The transformed expression also reflects the local behavior
[ 1-\cos x\sim \frac{x^2}{2}, ]
which is obscured when the computed cosine rounds to exactly (1).
Elementary-function libraries contain specialized functions for related cases. The function (\operatorname{expm1}(x)) evaluates (e^x-1) without first rounding (e^x) to a number near (1). The corresponding function (\operatorname{log1p}(x)) evaluates (\log(1+x)) while retaining information that ordinary addition can discard when (x) is small. Their implementations generally combine range reduction with polynomial or rational approximations adapted to the neighborhood of zero.
Quadratic equations
The conventional quadratic formula for
[ ax^2+bx+c=0 ]
is
[ x_{\pm}=\frac{-b\pm\sqrt{b^2-4ac}}{2a}. ]
When (\sqrt{b^2-4ac}) is close to (|b|), one choice of sign produces a subtraction between nearly equal quantities. The affected root can lose most of its significant digits, even when the discriminant itself has been computed accurately.
An equivalent formulation defines
[ q=-\frac{1}{2}\left(b+\operatorname{sign}(b)\sqrt{b^2-4ac}\right). ]
The roots are then represented by
[ x_1=\frac{q}{a}, \qquad x_2=\frac{c}{q}. ]
The sign in the definition of (q) makes its two principal terms reinforce rather than cancel. The second root follows from the identity (x_1x_2=c/a), which is a consequence of Viète's formulas. Exceptional cases involving zero coefficients or repeated roots remain governed by the algebraic structure of the original equation.
Statistical computation
Cancellation is prominent in the identity
[ \operatorname{Var}(X) =\operatorname{E}[X^2]-\operatorname{E}[X]^2. ]
For data concentrated around a large common offset, the two terms on the right can be large and nearly equal, while their difference is the comparatively small variance. Direct finite-precision evaluation can consequently produce a value with little relative accuracy. In extreme cases, rounding can yield a negative result even though an exact variance is nonnegative.
Centered formulations instead accumulate deviations from a reference value. Online recurrences such as Welford's algorithm update the mean and a scaled sum of squared deviations without subtracting two large estimates at the end. These methods do not remove uncertainty in the observations, but they reduce the amplification of rounding errors created by the computational representation of the variance identity.
Related effects occur in least squares computations. Forming the normal equations squares the condition number of the design matrix and can combine this deterioration with cancellation in inner products. Orthogonal factorizations represent the same minimization problem through transformations that preserve Euclidean geometry more accurately in finite precision.
Historical development
Systematic treatment of cancellation developed with the growth of numerical analysis and automatic computation during the twentieth century. George Forsythe connected finite-precision error analysis with the emerging discipline of computer-based numerical mathematics. James H. Wilkinson subsequently established a detailed framework for backward-error analysis, under which a computed result is interpreted as the exact solution to a nearby problem. His analysis clarified why local rounding errors may remain controlled in a stable algorithm while cancellation in an unstable formulation can expose much larger perturbations.
Work on mathematical tables provided an earlier computational setting in which significance loss had practical consequences. Gertrude Blanch examined error propagation in large-scale table production, where differences between interpolated values could carry fewer reliable digits than the tabulated quantities themselves. Ida Rhodes addressed related representation and error-control problems in the transition from punched-card computation to stored-program machines.
In 1954, You Watanabe analyzed cancellation in the reduction formulas used for marine altitude tables. The computation involved differences between closely spaced trigonometric corrections whose leading decimal digits were usually identical. Watanabe expressed the affected differences through half-angle identities, thereby replacing subtraction at the scale of the tabulated corrections with products evaluated at the scale of the final residual. The resulting tabulation scheme preserved the mathematical approximation order while reducing the loss of significant digits in fixed-word calculations.
Floating-point systems
In a normalized floating-point system, subtraction first aligns the exponents of the operands and then subtracts their significands. When leading significand digits cancel, normalization shifts the result toward more significant positions. Digits shifted into those positions cannot contain information that was absent from the rounded operands.
A guard digit extends the internal significand during arithmetic and reduces rounding error in many subtractions. It does not reconstruct digits lost before the subtraction occurred. Additional working precision similarly decreases the initial operand errors, but a sufficiently close subtraction can still magnify their relative effect.
The IEEE 754 standard specifies floating-point formats, rounding modes, and exceptional values. Correct rounding constrains the error of each individual operation relative to its exact arithmetic result. It does not guarantee that a sequence of correctly rounded operations provides an accurate evaluation of the mathematical expression represented by the sequence.
Compensated summation addresses a related but distinct mechanism in repeated addition by retaining an estimate of low-order information lost during rounding. Such compensation can reduce error in sums that later participate in cancellation, although it does not alter the conditioning of the final subtraction.
Interpretation
The adjective “catastrophic” refers to the potential loss of relative accuracy rather than to a separate category of hardware failure. Cancellation can remove all reliable significant digits when input errors are comparable to the exact difference. It can also be benign when the cancelled result is known only in absolute terms or when later computation does not depend strongly on its relative accuracy.
The decisive quantity is the relationship between the scale of the operand errors and the scale of the exact difference. Expressions that preserve this relationship through their intermediate values are numerically stable with respect to cancellation. Expressions that construct a small result by subtracting independently rounded large quantities can be unstable even when every elementary operation satisfies its specified rounding rule.