Floating point gotchas — catastrophic cancellation, associativity failure

1. WHAT is a floating point number?

WHY $2^{-52}$ ? With 52 fraction bits after the implicit leading 1, the least significant bit at exponent $0$ has weight $2^{-52}$ . That is the resolution near $1.0$ .

The key word is relative: error scales with the magnitude of the number, not absolutely.

2. Catastrophic cancellation

Formula Error amplification — derived

Let $a,b$ be exact, stored as $\hat a = a(1+\delta_a)$ , $\hat b=b(1+\delta_b)$ , $|\delta|\le u$ . Compute $r = a-b$ . The machine gives $\hat r = \hat a - \hat b$ . $\hat r - r = a\delta_a - b\delta_b.$ Relative error: $\left|\frac{\hat r - r}{r}\right| = \left|\frac{a\delta_a - b\delta_b}{a-b}\right| \le u\,\frac{|a|+|b|}{|a-b|}.$ The amplification factor is $\dfrac{|a|+|b|}{|a-b|}$ . When $a\approx b$ , the denominator $\to 0$ and the relative error blows up. The subtraction itself is exact (Sterbenz) — the damage was already baked into $\hat a,\hat b$ ; subtraction just reveals it.

Worked example Classic: the quadratic formula

Solve $x^2 - 200000x + 1 = 0$ . Roots via $x=\dfrac{-b\pm\sqrt{b^2-4ac}}{2a}$ with $a=1,b=-200000,c=1$ . $\sqrt{b^2-4ac}=\sqrt{40000000000-4}\approx 199999.99999$ . The "+" root: $x_+ = \frac{200000+199999.99999}{2}\approx 199999.999995$ — fine (adding similar-sign numbers). The "−" root: $x_- = \frac{200000-199999.99999}{2}$ — catastrophic cancellation! Two ~200000 numbers subtract to ~0.00001.

Fix (WHY it works): use the identity $x_+x_-=c/a$ . Compute the stable root first, then $x_- = \frac{c}{a\,x_+}.$ No subtraction of near-equals → relative error stays $\sim u$ . Why this step? Multiplication/division never amplify relative error; we route around the dangerous subtraction.

Figure — Floating point gotchas — catastrophic cancellation, associativity failure

3. Associativity failure

Definition Kahan summation (the trick that recovers lost bits)

s = 0.0; c = 0.0
for x in data:
    y = x - c          # add back last lost bit
    t = s + y          # may lose low bits of y
    c = (t - s) - y    # recover exactly what was lost
    s = t

WHY it works: (t - s) is the part of y that actually got added; subtracting y gives the negated part that was dropped. We carry it into the next iteration.

4. Common mistakes (steel-manned)

5. Recall

Recall Active recall — cover the answers

What's the relative-error amplifier in $a-b$ ? → $\dfrac{|a|+|b|}{|a-b|}$ .
Is float subtraction of near-equal numbers itself inaccurate? → No, it's exact; it just exposes prior error.
Why does $(a+b)+c\neq a+(b+c)$ ? → Each + rounds at a place that depends on the partial sum's magnitude.
Fix for the small quadratic root? → $x_- = c/(a x_+)$ .
What does Kahan summation track? → The low-order bits lost in each addition.

Recall Feynman: explain to a 12-year-old

Imagine your calculator can only show 4 digits. Write $12340000$ and add $1$ — the calculator still shows $12340000$ , the $1$ just fell off the edge. Now if two giant numbers are almost the same, like $12340000$ and $12340000$ , and you subtract them, the calculator says $0$ — but the real answer might have been a tiny number that got eaten earlier. So big-minus-big is dangerous: the answer is small but the mistakes are big. And $1+\text{(huge)}+(-\text{huge})$ can be $0$ if you do it left-to-right but $1$ if you cancel the huge ones first — the order of adding changes the answer!

Flashcards

What is machine epsilon for IEEE-754 double?

2^{-52}\approx 2.22\times10^{-16}

, the gap between

1.0

and the next representable double.

State the floating rounding model.

\text{fl}(x)=x(1+\delta)

with

|\delta|\le u=\tfrac12\varepsilon_{\text{mach}}

What is catastrophic cancellation?

Loss of significant digits when subtracting two nearly-equal numbers; small absolute errors become large relative errors.

Relative-error amplification factor for

a-b

\dfrac{|a|+|b|}{|a-b|}

, which blows up as

a\to b

Is the subtraction step itself the source of error?

No — for near-equal operands it's exact (Sterbenz); it only reveals error already present in the operands.

Stable way to get the small root of

x^2+bx+c

Compute the large-magnitude root, then use

x_2=c/(a x_1)

(product of roots).

Stable form of

1-\cos x

near 0?

2\sin^2(x/2)

Stable form of

\sqrt{x+1}-\sqrt{x}

\dfrac{1}{\sqrt{x+1}+\sqrt{x}}

Why is float addition not associative?

Each + rounds at a place that depends on the running magnitude; different groupings round differently.

Give values where

(a+b)+c\neq a+(b+c)

a=1,b=10^{16},c=-10^{16}

→ gives 0 vs 1.

What error does naive summation of

n

terms accumulate?

\sim (n-1)\,u\sum|x_i|

, growing with

n

What does Kahan summation achieve and how?

Reduces sum error to

\sim u

(independent of

n

) by carrying the lost low-order bits in a compensation variable.

Why is 0.1+0.2==0.3 False?

None of those are exactly representable in binary; rounded sum differs from rounded 0.3 by

\sim10^{-17}

Correct way to compare floats?

Tolerance test: abs(x-y) <= atol + rtol*max(|x|,|y|) (e.g. math.isclose).

Connections

IEEE-754 floating point representation
Numerical stability and conditioning
Kahan compensated summation
Quadratic formula numerical issues
Catastrophic cancellation
Round-off error propagation
Relative vs absolute error
NumPy dtypes and precision

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho, computer real numbers ko exactly store nahi kar sakta — har double ke paas sirf ~15-16 significant digits hote hain (machine epsilon $\approx 2.2\times10^{-16}$ ). Normally itna kaafi hai, lekin do jagah dimaag kaam karna band kar deta hai. Pehla: catastrophic cancellation. Jab tum do bade aur lagbhag barabar numbers ko subtract karte ho, answer chhota nikalta hai par jo chhoti-chhoti errors pehle se chhupi thi, woh relative terms mein bahut bada ho jaati hai. Subtraction khud galat nahi karta — woh to exact hai — bas pehle se baked error ko expose kar deta hai. Amplification factor hota hai $\frac{|a|+|b|}{|a-b|}$ , jo $a\approx b$ pe explode karta hai.

Iska fix? Formula ko rewrite karo taaki near-equal subtraction aaye hi na. Jaise quadratic formula mein chhoti root ke liye $x_2 = c/(a x_1)$ use karo, ya $1-\cos x$ ki jagah $2\sin^2(x/2)$ . Yaad rakho: zyada precision (float128) ya zyada terms add karna problem solve nahi karega — asli problem expression ki conditioning hai, formula badalna padega.

Doosra gotcha: associativity failure. Maths mein $(a+b)+c = a+(b+c)$ , par floats mein nahi! Kyunki har + apne aap round karta hai. Example: $a=1$ , $b=10^{16}$ , $c=-10^{16}$ . Left-to-right karo to $1+10^{16}$ ka chhota $1$ "gir" jaata hai (absorption), phir $-10^{16}$ se $0$ milta hai. Par agar pehle $b+c=0$ karo, phir $+1$ , to answer $1$ aata hai! Isliye lambi summation mein chhote numbers pehle add karo, ya Kahan summation use karo jo lost bits ko ek compensation variable mein track karta hai. Aur kabhi floats ko == se compare mat karo — tolerance (math.isclose) use karo.

Floating point gotchas — catastrophic cancellation, associativity failure

1. WHAT is a floating point number?

2. Catastrophic cancellation

3. Associativity failure

4. Common mistakes (steel-manned)

5. Recall

Flashcards

Connections

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Scientific Computing (Python)

Connections