Every stored number carries a tiny relative error, at most $u \approx 10^{-16}$ (see Floating-Point Numbers). Usually that is harmless. But subtracting two nearly equal numbers can turn tiny relative errors into a huge one. The cure is often algebra you already know, such as rationalizing with a conjugate (Adding and Multiplying Radicals).
Key idea
When $a \approx b$, the leading digits of $a - b$ cancel, and the digits that remain come from the rounding errors of $a$ and $b$. Avoid the subtraction by rewriting the formula: $\sqrt{x + 1} - \sqrt{x} = \frac{1}{\sqrt{x + 1} + \sqrt{x}}$.
Why it works
Suppose $a$ and $b$ are stored with absolute errors $\delta_a$ and $\delta_b$, each at most $u|a|$. The subtraction itself is nearly exact, but its result inherits both errors: $$\frac{|(\tilde{a} - \tilde{b}) - (a - b)|}{|a - b|} \le \frac{u(|a| + |b|)}{|a - b|}.$$ The factor $\frac{|a| + |b|}{|a - b|}$ is huge when $a \approx b$. If $a$ and $b$ agree in their first $d$ digits, it is about $10^{d}$: roughly $d$ correct digits are lost.
Worked example: Cancellation in 4-digit arithmetic
Compute $\sqrt{1001} - \sqrt{1000}$, rounding every result to 4 significant digits.
- $\sqrt{1001} = 31.6386\ldots \to 31.64$ and $\sqrt{1000} = 31.6228\ldots \to 31.62$.
- Subtract: $31.64 - 31.62 = 0.02$.
- The true value is $0.015807\ldots$: the computed one has only 1 significant digit and is off by $27\%$.
Answer: $0.02$, with only one correct digit
Worked example: Rewrite to avoid it
Compute the same quantity as $\frac{1}{\sqrt{1001} + \sqrt{1000}}$ in 4-digit arithmetic.
- Multiply by the conjugate: $(\sqrt{1001} - \sqrt{1000})\cdot\frac{\sqrt{1001} + \sqrt{1000}}{\sqrt{1001} + \sqrt{1000}} = \frac{1001 - 1000}{\sqrt{1001} + \sqrt{1000}}$.
- Denominator: $31.64 + 31.62 = 63.26$. Then $1 \div 63.26 = 0.015807\ldots \to 0.01581$.
- All 4 digits are right. The same rounded roots went in; only the formula changed.
Answer: $0.01581$
Worked example: Cancellation in double precision
For $x = 10^{-8}$, a computer evaluates $1 - \cos x$ as $0$. What happened, and what is the fix?
- $\cos(10^{-8}) = 1 - 5 \times 10^{-17} + \cdots$, which is closer to $1$ than half the gap above or below $1$, so it is stored as exactly $1$.
- Then $1 - 1 = 0$: every digit was lost, although the true value is about $5 \times 10^{-17}$.
- Use $1 - \cos x = 2\sin^{2}\frac{x}{2}$: $2\sin^{2}(5 \times 10^{-9}) \approx 5 \times 10^{-17}$, correct to full precision.
Answer: Use $2\sin^{2}(x/2)$.
- $\sqrt{x + 1} - \sqrt{x} = \dfrac{1}{\sqrt{x + 1} + \sqrt{x}}$ for large $x$.
- $1 - \cos x = 2\sin^{2}(x/2)$ for small $x$.
- $\ln(x + 1) - \ln x = \ln(1 + 1/x)$ for large $x$.
- For small $x$, $e^{x} - 1 = x + \frac{x^{2}}{2} + \cdots$ (a library function
expm1does this).
Cancellation is not a bug in the subtraction: the computer subtracts the two stored numbers exactly. The damage was done earlier, when $a$ and $b$ were rounded; subtraction only exposes it.
Common mistake
Trusting every digit a computer prints. After cancellation the leading digits are gone, and most of what is printed is round-off. Quick check: if the two numbers you subtract agree in their first $d$ digits, expect to lose about $d$ of your roughly 16 digits.