Exercises — Floating point gotchas — catastrophic cancellation, associativity failure

1 → (A). Dono square roots $\approx 10^6$ hain aur almost equal hain; near-twins subtract karne se hidden relative error expose ho jaati hai. Amplifier $\frac{|a|+|b|}{|a-b|}$ bahut bada hai. 2 → (B) absorption. Har term $10^{-9}$ running sum $\sim 10^9$ ke comparison mein astronomically chota hai. $10^9$ ke paas representable doubles ke beech ka gap approximately $10^9{\epsilon }_{\text{mach}}\approx 2\times 10^{-7}$ hai, aur $10^{-9}$ us gap se bahut neeche hai → har add kuch nahi deta. Dekho Catastrophic cancellation ka cousin, absorption. 3 → (C). Multiplication relative error amplify nahi karta; product $\le u$ relative error ke saath store hota hai. Safe hai. 4 → (A). $e^{10^{-10}}\approx 1+10^{-10}$; ise store karne par interesting part almost round ho jaata hai, phir $1$ subtract karne se ek toot-phoot result milta hai. Fix: math.expm1 use karo.

1 → True. $\text{fl}(a+b)$ aur $\text{fl}(b+a)$ ek hi real number round karte hain, toh dono exactly agree karte hain. 2 → False. Har + partial sum ki magnitude ke hisaab se ek jagah round karta hai; regrouping alag tarike se round karta hai. 3 → False. Sterbenz lemma ke according (is page ke upar define kiya gaya hai), jab $a,b$ factor of $2$ ke andar hain toh subtraction exact hota hai. Yeh sirf woh error expose karta hai jo stored operands mein already baki thi.

WHAT: numbers ko derived amplifier mein dalo. $|a|+|b|=1.9999999$, aur $|a-b|=10^{-7}$. $\frac{|a|+|b|}{|a-b|}=\frac{1.9999999}{10^{-7}}=1.9999999\times 10^7\approx 2.0\times 10^7.$ Worst-case relative error $=u\times 2.0\times 10^7\approx 1.11\times 10^{-16}\times 2.0\times 10^7\approx 2.2\times 10^{-9}$. WHY iska matlab kya hai: humne $\sim 10^{-16}$ relative error se shuru kiya aur use $\sim 10^{-9}$ tak blow up kar diya — humne almost 7 decimal digits kho diye, exactly amplifier ka ${\log }_{10}$.

Pehla expression: $1.0+10^{16}$. Sach mein sum $10^{16}+1$ hai. Do candidate representable results hain: $10^{16}$ (neeche) aur $10^{16}+2$ (upar, ek pura gap). Sach mein value $10^{16}+1$ par hai, jo dono ke exactly beech mein hai. IEEE-754 round-to-nearest, ties-to-even use karta hai: woh us neighbour ko pick karta hai jiski last mantissa bit $0$ (even) ho. Yahan $10^{16}$ ki last bit $0$ hai, toh tie neeche $10^{16}$ ki taraf round hoti hai. Phir $-10^{16}=0.0$. Prints 0.0. Doosra expression: $10^{16}-10^{16}=0.0$ exactly, phir $+1.0=1.0$. Prints 1.0. Same teen numbers, sirf brackets alag — answers 100% se different hain. Yeh absorption ke through associativity failure hai. (Tie-to-even detail isliye hai ki $1$ kyun gayab hota hai; even tie se alag, koi bhi addend $1$ se chota waise bhi round down ho jaata.)

WHAT/WHY: $b<0$ hai, toh $-b>0$; + branch same-sign numbers add karta hai → safe root pehle. $\sqrt{b^2-4ac}=\sqrt{10^{16}-4}\approx 99999999.9999999998$, matlab $10^8$ se thoda kam. $x_{+}=\frac{-b+\sqrt{b^2-4ac}}{2a}=\frac{10^8+99999999.9999999998}{2}\approx \mathrm{99999999.99999999.}$ Ab bina subtraction ke dangerous root: $x_{-}=\frac{c}{a{x}_{+}}=\frac{1}{99999999.99999999}\approx 1.0000000000000001\times 10^{-8}.$ Check: $x_{+}{x}_{-}=c/a=1$ ✓ aur $x_{+}+x_{-}=-b/a=10^8$ ✓. Naive $x_{-}=\frac{-b-\sqrt{\dots }}{2a}=\frac{10^8-99999999.9999999998}{2}$ do $\sim 10^8$ numbers subtract karta hai → catastrophic. Dekho Quadratic formula numerical issues.

Naive: $\sqrt{10^{12}+1}\approx 1000000.0000005$ aur $\sqrt{10^{12}}=1000000.0$. Unka difference $\sim 5\times 10^{-7}$ hai, lekin har root mein $\sim 10^{-16}$ relative error hai $\Rightarrow$ har ek mein absolute error $\sim 10^{-10}$; near-twins subtract karne par amplifier $\frac{2\times 10^6}{5\times 10^{-7}}\approx 4\times 10^{12}$ se sab kuch barbaad ho jaata hai. Rewrite (WHY): conjugate se multiply karo — yeh near-equals ki subtraction ko denominator mein ek addition se replace kar deta hai: $g(x)=(\sqrt{x+1}-\sqrt{x})\cdot \frac{\sqrt{x+1}+\sqrt{x}}{\sqrt{x+1}+\sqrt{x}}=\frac{1}{\sqrt{x+1}+\sqrt{x}}.$ Stable value: $\frac{1}{\sqrt{10^{12}+1}+\sqrt{10^{12}}}\approx \frac{1}{2000000.0000005}\approx 5.0\times 10^{-7}$. Figure dekho: red "near-twin" bars subtract hokar ek sliver bante hain; blue rewrite us sliver ko bina cancellation ke directly compute karta hai.

Kyun $0$: $\cos (10^{-8})=1-\frac{1}{2}(10^{-8}{)}^2+\cdots =1-5\times 10^{-17}$. Lekin $1.0$ ke paas sabse chota step ${\epsilon }_{\text{mach}}=2.22\times 10^{-16}$ hai, aur $5\times 10^{-17}$ half a step se bhi chota hai $\Rightarrow$ $\cos x$ exactly $1.0$ par round ho jaata hai. Phir $1-1=0$, aur $0/x^2=0$. Total loss. Stable: $x/2=5\times 10^{-9}$ ke saath, $\sin (x/2)/(x/2)\to 1$ (tiny arguments ke liye accurately compute hota hai), toh $\frac{1}{2}{\left(\frac{\sin (x/2)}{x/2}\right)}^2\approx \frac{1}{2}(1{)}^2=\mathrm{0.5.}$ Relative error $\sim u$ — perfect.

Rule: digits lost $\approx {\log }_{10}(\text{amplifier})$. ${\log }_{10}(10^9)=9$ digits lost. Survivors $\approx 16-9=7$ significant decimal digits. Yahi amplifier ka practical matlab hai: uska base-10 log digit death toll hai. Dekho Round-off error propagation.

Loop yaad karo: y = x - c; t = s + y; c = (t - s) - y; s = t. Jo facts use honge: $10^{16}$ ke paas gap $2.0$ hai, toh wahan integers sirf tab representable hain jab even hon; $10^{16}$ aur $10^{16}+2$ representable hain, $10^{16}+1$ nahi hai.

Naive left-to-right: $((1+10^{16})+1)-10^{16}$. $\text{fl}(1+10^{16})=10^{16}$ ($1$ absorb ho gaya), $\text{fl}(10^{16}+1)=10^{16}$ (phir absorb), phir $-10^{16}=0$. Naive result $=0.0$ — $2$ ka error hai.

Kahan trace (start $s=0.0,c=0.0$). Har line mein: WHAT operation hai, phir rounded value:

• $x=1$: y = 1 - 0 = 1 (exact). t = fl(0 + 1) = 1 (exact). c = fl((1 - 0) - 1) = 0. s = 1. → $s=1,c=0$.
• $x=10^{16}$: y = fl(1e16 - 0) = 1e16 (exact). t = fl(1 + 1e16) = 1e16 — $1$ half gap se neeche hai, absorb ho gaya. Ab recover karo: t - s = fl(1e16 - 1) = 1e16 (phir absorb, exact difference $1e16-1$ round up hokar $1e16$ ban gaya), phir c = fl((t - s) - y) = fl(1e16 - 1e16) = 0. Hmm — toh is simple integer data par Kahan c = 0 store karta hai. → $s=10^{16},c=0$. (WHY khoya hua $1$ abhi capture nahi hua: t-s aur recovery dono exact grid points par land kiye, toh is step mein koi residual surface nahi hua — loss implicitly is fact mein carry ho raha hai ki s $1$ kam hai.)
• $x=1$: y = fl(1 - 0) = 1 (exact). t = fl(1e16 + 1) = 1e16 — absorb phir. t - s = fl(1e16 - 1e16) = 0, toh c = fl(0 - 1) = -1. Ab dropp hua $1$ capture ho gaya: $c=-1$. s = 1e16. → $s=10^{16},c=-1$.
• $x=-10^{16}$: y = fl(-1e16 - (-1)) = fl(-1e16 + 1) = -1e16 ($+1$ absorb ho gaya, lekin woh y ki intent mein held hai). t = fl(1e16 + (-1e16)) = 0 (exact cancellation). t - s = fl(0 - 1e16) = -1e16, c = fl((-1e16) - (-1e16)) = 0. s = 0. → $s=0,c=0$.

Final s = 0.0 is exact IEEE trace ke saath. $\pm 10^{16}$ ka akele $1$'s ke aas-paas yeh single interleaving Kahan ko bhi yahan defeat kar deta hai, kyunki compensation $c=-1$ khud $-10^{16}$ mein re-add hone par absorb ho jaata hai. Lesson: Kahan us subnormal-relative addend ki pure absorption ke khilaf magic nahi hai jo baad mein cancel ho jaati hai — cure hai reorder karna (giants pehle cancel karo). Yahi Exercise 5.3 hai.

Contrast — ek order jahan Kahan kaam karta hai. $[10^{16},1,1,-10^{16}]$ par, naive $0$ deta hai, lekin $[1,1,10^{16},-10^{16}]$ left-to-right sum deta hai $\text{fl}(\text{fl}(\text{fl}(1+1)+10^{16})-10^{16})=\text{fl}(\text{fl}(2+10^{16})-10^{16})$; kyunki $10^{16}+2$ representable hai, yeh hai $\text{fl}((10^{16}+2)-10^{16})=2$. Exact. Moral yehi hai: order beats absorption; Kahan tab help karta hai jab losses residuals hote hain, total absorptions nahi jinke terms baad mein cancel ho jaate hain.

Predicate: $|x-y|\le \max (\text{rtol}\cdot \max (|x|,|y|),\text{atol}).$

• rtol (relative tolerance) operands ki magnitude ke saath scale hota hai — zaruri hai kyunki float error relative hoti hai.
• atol (absolute tolerance) us case ko rescue karta hai jab dono $0$ ke paas hain (wahan relative test degenerate ho jaata hai). $0.1+0.2$ case: computed sum $0.30000000000000004$ hai, $0.3$ se $\approx 5.55\times 10^{-17}$ differ karta hai. Threshold $=1\times 10^{-9}\times 0.3=3\times 10^{-10}$. Kyunki $5.55\times 10^{-17}\le 3\times 10^{-10}$, woh close HAIN → predicate True return karta hai, bhaley hi == False return kare.

Step 1 (WHAT): computed result expand karo. $\hat{r}=\hat{a}-\hat{b}=a(1+{\delta }_a)-b(1+{\delta }_b)=(a-b)+(a{\delta }_a-b{\delta }_b).$ Step 2: sach wala $r=a-b$ subtract karo: $\hat{r}-r=a{\delta }_a-b{\delta }_b.$ Step 3 (numerator bound karo): triangle inequality aur $|\delta |\le u$ se, $|a{\delta }_a-b{\delta }_b|\le |a||{\delta }_a|+|b||{\delta }_b|\le u(|a|+|b|).$ Step 4 ($|r|=|a-b|$ se divide karo): $\left|\frac{\hat{r}-r}{r}\right|=\frac{|a{\delta }_a-b{\delta }_b|}{|a-b|}\le u\frac{|a|+|b|}{|a-b|}.■$ WHY "exact subtraction" assumption fair hai: Sterbenz lemma guarantee karta hai ki $\frac{1}{2}a\le b\le 2a$ hone par koi nayi rounding nahi hoti; saara damage ${\delta }_a,{\delta }_b$ mein rehta hai, jo precisely wahi hai jo proof isolate karta hai.

Step 1 (WHAT gap hai): $L$ ke paas representable doubles ke beech ki spacing hai: $\text{gap}(L)=2^{\lfloor {\log }_{2}L\rfloor }\cdot 2^{-52}=2^{\lfloor {\log }_{2}L\rfloor -52}.$ Yeh $L$ ke exponent par least-significant mantissa bit ki weight hai. Step 2 (round-to-nearest rule): sach wali value $L+s$ do neighbours $L$ aur $L+\text{gap}(L)$ ke beech hai. Round-to-nearest tab $L$ par snap karta hai jab woh $L$ se at most half a gap upar ho: $s\le \frac{1}{2}\text{gap}(L)=2^{\lfloor {\log }_{2}L\rfloor -53}.$ Exactly half gap par, ties-to-even decide karta hai: agar $L$ ki last mantissa bit $0$ (even) hai toh tie bhi $L$ ki taraf round hoti hai, toh strict absorption region $s\le \frac{1}{2}\text{gap}(L)$ hai even-$L$ ke liye (aur otherwise $s<\frac{1}{2}\text{gap}(L)$). Step 3 ($L=2^{53}$ apply karo): $\lfloor {\log }_{2}L\rfloor =53$, toh $\text{gap}(2^{53})=2^{53-52}=2^1=2,\frac{1}{2}\text{gap}=2^{53-53}=2^0=1.$ Isliye koi bhi $s\le 1$ fully absorb ho jaata hai: $\text{fl}(2^{53}+1)=2^{53}$. Wakai $2^{53}+1$ pehla positive integer hai jo double represent nahi kar sakta — ek famous landmark: doubles $2^{53}$ tak har integer represent karte hain, phir skip karna shuru kar dete hain.

Bura order $[10^{16},1,1,-10^{16}]$: absorb, absorb, phir cancel → $0$. Achha order $[10^{16},-10^{16},1,1]$: giants ko pehle cancel karo ($10^{16}-10^{16}=0$ exactly), phir $0+1+1=2$. Exact. Principle: bade opposite-sign terms ko ek doosre ke saath kill karo pehle, taaki woh chote survivors ko nigal na sakein. Jab aap reorder nahi kar sakte (streaming data), residual losses ke liye Kahan use karo — lekin jaise Exercise 4.1 ne dikhaya, Kahan ek total absorption ko bhi rescue nahi kar sakta jo baad mein cancel ho, isliye reordering primary weapon hai. Yahi associativity-failure lesson ek strategy mein badal gaya hai.

• $10^9$ ke amplifier se kitne digits jaate hain? ::: lagbhag $9$ (yaani uska ${\log }_{10}$), $\sim 7$ bachte hain.
• $\sqrt{x+1}-\sqrt{x}$ ka stable rewrite? ::: $\frac{1}{\sqrt{x+1}+\sqrt{x}}$.
• Pehla integer jo double represent nahi kar sakta? ::: $2^{53}+1$.
• math.isclose predicate? ::: $|x-y|\le \max (\text{rtol}\cdot \max (|x|,|y|),\text{atol})$.
• $[10^{16},-10^{16},1,1]$ ka exact sum left-to-right? ::: $2.0$ (giants pehle cancel karo).
• Quadratic root kaunsa directly compute karte ho, sign-wise? ::: woh jiska $\pm$, $-b$ ke sign se match kare (same-sign addition).