Why does this naive solution to catastrophic cancellation not work?

Question

I see on wikipedia that catastrophic cancellation is a phenomena where B~=A then A-B will have very high relative error compared to the true difference.

A quite naive solution occurred to me: why not just take: A-B~=(NA-NB)/N s.t. N>>1? This would make the 'true difference' much larger and should therefore decrease the relative error of approximating A-B by a lot right?

Answer 1

I see on wikipedia that catastrophic cancellation is a phenomena where B~=A then A-B will have very high relative error compared to the true difference.

That's not what catastrophic cancellation is, and that's not what Wikipedia says.

In fact, if A and B are even modestly nearby floating-point numbers, close enough that B/2 ≤ A ≤ B, then by the Sterbenz lemma, A − B is a floating-point number too and so floating-point subtraction A ⊖ B = fl(A − B) will compute A − B exactly with zero error.

Catastrophic cancellation happens when you don't have A and B themselves—instead you have approximations A′ and B′ to true values A and B, and you want the difference A − B. These approximations might arise for many reasons: from measurement error, from series truncation, from rounding, etc.

Even if you can compute the exact difference A′ − B′ (and in floating-point arithmetic, when A′ and B′ are close enough, you can!), the relative error of the difference of approximations A′ − B′ can be very large—it's inversely proportional to the difference A − B of the true values. That's catastrophic cancellation.

Specifically, the relative error of A′ − B′ from A − B is |A𝛿 − B𝜇|/|A − B|, where 𝛿 = (A − A′)/A and 𝜇 = (B − B′)/B, so that |𝛿| is the relative error of A′ from A and |𝜇| is the relative error of B′ from B.

I quite naive solution occurred to me: why not just take: A-B~=(NA-NB)/N s.t. N>>1? This would make the 'true difference' much larger and should therefore decrease the relative error of approximating A-B by a lot right?

This doesn't accomplish anything.

If you have approximations A′ and B′ and you are able to compute (NA′ − NB′)/N = A′ − B′ exactly, well, the result would still be subject to catastrophic cancellation. But it's worse, because your suggestion is to compute (N⊙A′ ⊖ N⊙B′)⊘N = fl(fl(fl(NA′) − fl(NB′))/N), incurring many additional rounding errors (unless N is a power of the floating-point radix), and possibly incurring overflow or underflow as well.

The only way to avoid catastrophic cancellation is to avoid trying to subtract approximations of nearby quantities. For example:

• Instead of measuring two sticks with a ruler and subtracting the lengths you measured, lay the sticks side by side with one end of each stick aligned and measure the distance between the unaligned ends directly.
• Instead of computing exp(x) = 1 + x + x²/2 + x³/3! + x⁴/4! + ⋯ and then subtracting 1 from it when you want exp(x) − 1 for x near 0, rewrite it as exp(x) − 1 = x + x²/2 + x³/3! + x⁴/4! + ⋯ and compute that directly without subtraction.
  • In a math library, you can do this with the expm1 procedure.
• Instead of computing (1 − fl(cos(t)))/2 for t near 0 with a table of cosines in a historic math library, compute fl(haversin(t)) with a table of (logarithmic) haversines (or use sin(t/2)**2 in a modern math library).

---

The currently accepted answer is wrong and gives a dangerous misconception about the relation between floating-point arithmetic and catastrophic cancellation:

Catastrophic cancellation happens because M only has a limited number of bits, and M_A is approximately M_B so the high bits cancel.

Catastrophic cancellation does not happen because of limited number of bits in the output—the Sterbenz lemma proves that the output of floating-point subtraction is exact when the inputs are close enough!

Catastrophic cancellation happens when the inputs to the subtraction are themselves approximations with some error—again, whether that error is from measurement, series truncation, rounding, etc.

Even if you had infinitely many bits in your representation of A′, B′, and A′ − B′, using A′ − B′ as an approximation to A − B would still have relative error proportional to 1/(A − B). In technical terms, subtraction is ill-conditioned at nearby inputs, just like log is ill-conditioned near 1.

Catastrophic cancellation is a fundamental property of the mathematical subtraction operation, independent of floating-point representations, and it applies whether or not the output of subtraction is rounded.