Catastrophic Cancellation: A Floating-Point Error

1. Why Computers Can't Be Perfectly Precise

Before we can understand what goes wrong in a calculation, we must first understand how the calculation is performed. On a computer, real numbers are not stored with infinite precision. They are approximated using a system called floating-point arithmetic.

The core idea is to represent a number in a form of scientific notation, but in base-2: a significand (the significant digits) and an exponent. For example, a number might be stored as 1.01101... × 2⁵. However, computers have a finite number of bits (usually 32 or 64) to store both the significand and the exponent. This has two immediate consequences:

1. Representation Error: Some decimal fractions that are simple for us (like 0.1) have an infinitely repeating representation in binary, much like 1/3 is 0.333... in decimal. Since the computer has to truncate this at some point, the stored value is only an approximation.
2. Accumulation of Error: When you perform calculations with these approximate numbers, the small errors can add up.

The following video provides an excellent introduction to this problem.

The key insight is that because of the finite number of bits in the significand, there are "gaps" between the numbers that a computer can represent. The size of these gaps gets larger as the magnitude of the numbers increases.

The following reading explores this concept of "spacing" with some practical Python examples.

The example where 1e25 + 1e9 == 1e25 is striking. The gap between 1e25 and the next representable number is so large (over 2 billion!) that adding 1 billion isn't enough to "cross the mountain peak" to the next value. This loss of information is a key type of floating-point error, but it is not catastrophic cancellation. Catastrophic cancellation is something more subtle and dangerous.

2. Catastrophic Cancellation: The Anatomy of a Disaster

Now we're ready to tackle the main subject.

Catastrophic cancellation is the extreme loss of precision that occurs when subtracting two nearly equal numbers.

Let's say we have two numbers, $x$ and $y$, that are very close to each other. When the computer stores them, it introduces small representation errors. Let's denote the floating-point representations as fl(x) and fl(y).

• fl(x) = x(1 + ε₁)
• fl(y) = y(1 + ε₂)

Here, ${\epsilon }_1$ and ${\epsilon }_2$ are the small relative errors from the initial representation. Now, what happens when the computer calculates fl(x) - fl(y)?

The result is x(1 + ε₁) - y(1 + ε₂) = (x - y) + (xε₁ - yε₂)

The true answer is (x - y). The error in the result is the term (xε₁ - yε₂). The problem arises when we look at the relative error:

$\text{Relative Error}=\frac{\text{Absolute Error}}{\text{True Value}}=\frac{x{ϵ}_1-y{ϵ}_2}{x-y}$

If $x$ is very close to $y$, the denominator (x - y) becomes very small. Even if the numerator (xε₁ - yε₂) is also small, dividing by a much smaller number can make the relative error enormous. The leading, correct significant digits cancel each other out, leaving you with a result dominated by the noise from the representation errors.

This is "catastrophic" because you can lose almost all of your correct significant digits in a single operation. The following resource provides a formal analysis and a clear example.

This phenomenon is vividly illustrated in the following plot. It shows the error when computing sqrt(1+x) - sqrt(1-x). For very small x, sqrt(1+x) and sqrt(1-x) are nearly equal, creating a perfect scenario for catastrophic cancellation.

3. Avoiding Catastrophe

The good news is that catastrophic cancellation is often a flaw in the formula, not an unavoidable law of physics. It can frequently be fixed by rewriting the expression in a way that avoids the subtraction of two nearly equal numbers.

Let's look at two classic examples of this.

In both cases—calculating 1 - cos(x) and solving the quadratic equation—a simple algebraic reformulation turns a numerically unstable calculation into a stable one. This principle of reformulating expressions to avoid numerical pitfalls is a central theme in numerical analysis.

Conclusion

In this lesson, we have uncovered the hidden dangers of floating-point arithmetic.

Key Takeaways:

• Computers approximate real numbers using a finite-precision format (floating-point), leading to representation errors and non-uniform gaps between representable numbers.
• Catastrophic cancellation is a severe loss of precision that occurs when subtracting two nearly equal numbers.
• The subtraction cancels out the accurate, leading significant digits, leaving a result dominated by the initial, small representation errors.
• This is not a flaw in the computer's hardware but a vulnerability in mathematical expressions. It can often be fixed by reformulating the expression to avoid the problematic subtraction.

Preview of the Next Lesson:

Now you have the tool you need to diagnose the failure we saw in our first lesson. In the next lesson, we will analyze why the single-pass variance formula is numerically unstable. We'll see that the "textbook" formula, E[X²] - (E[X])², is a textbook case of catastrophic cancellation when the standard deviation is small relative to the mean, setting the stage perfectly for introducing Welford's algorithm as the solution.