Floating point gotchas — catastrophic cancellation, associativity failure: Visual walkthrough

5.4.22 · D2 · Coding › Scientific Computing (Python) › Floating point gotchas — catastrophic cancellation, associat

Step 1 — Ek number line jisme gaps hain

KYA HAI. Ek real number line smooth hoti hai: kisi bhi do points ke beech hamesha ek aur point hota hai. Ek computer's number line smooth nahi hoti. Woh sirf dots ke ek finite set par land kar sakti hai. Neighbouring dots ke beech ek gap hota hai — ek aisa interval jisme koi representable number hi nahi hota.

KYU. Ek double ke paas bits ka ek fixed budget hota hai (dekho IEEE-754 floating point representation). Fixed bits ka matlab hai dots ki ek finite number. "Lost digits" ki poori baat aslmein yeh hai: "tumhara true value ek gap mein gir gaya aur nearest dot par snap ho gaya."

PICTURE. Figure dekho. $1.0$ ke paas dots close hain; $1000$ ke paas woh dur hain. Spacing relative hai — number ke size ke saath badhti hai.

Figure — Floating point gotchas — catastrophic cancellation, associativity failure

Yahan sabse important word relative hai: grid chhote numbers ke liye fine hai aur bade numbers ke liye coarse.

Step 2 — Rounding: nearest dot par snapping

KYA HAI. Jab tumhara true value $x$ koi dot nahi hota, computer nearest dot store karta hai. Stored value ko hum $fl (x)$ kehte hain (padho "float of $x$ ").

KYU. Jo representable nahi hai usse store nahi kar sakte. Nearest-dot rounding sabse kam bura choice hai: error at most half a gap hoti hai, kyunki agar aap half gap se zyada door hote, toh doosra dot closer hota.

PICTURE. Red arrow true $x$ dikhata hai; violet dot wahan hai jahan woh land karta hai. Error chhote segment ki length hai, aur woh kabhi half gap (shaded band) se zyada nahi ho sakti.

Yeh tool — har stored number ko true value times $(1 + δ)$ likhna — hi poori wajah hai ki hum algebraically error track kar sakte hain. Do flavours ke liye dekho Relative vs absolute error.

Step 3 — Do almost-equal numbers, har ek apna wobble liye

KYA HAI. Do exact numbers $a$ aur $b$ lo jo value mein close hain. Computer $\overset{a}{^} = a (1 + δ_{a})$ aur $\hat{b} = b (1 + δ_{b})$ hold karta hai.

KYU. Hum unhe subtract karna chahte hain. Pehle hume honest rehna hoga: koi bhi input exact nahi hai. Har ek already ek absolute error $a δ_{a}$ aur $b δ_{b}$ carry karta hai. Kyunki $a$ aur $b$ bade hain, yeh absolute errors tiny nahi hain — woh $\sim u \times (bada number)$ hain.

PICTURE. Do tall bars, $a$ aur $b$ , almost same height. Har ek ke upar ek chhota "fuzz" band baitha hai — absolute error. Notice karo ki fuzz tall bar ka ek fixed fraction hai, toh absolute terms mein woh chunky hai.

In do chunky fuzz-bands par nazar rakho. Yeh ek subtraction mein bachne wale hain jo answer ko kuch nahi kar dega.

Step 4 — Subtraction: answer shrink ho jaata hai, fuzz nahi

KYA HAI. $r = a - b$ (true) versus $\overset{r}{^} = \overset{a}{^} - \hat{b}$ (stored) compute karo. Do lines subtract karo.

KYU. Yahi crime ka moment hai. Tall bars cancel hokar ek tiny sliver $r = a - b$ mein aa jaate hain. Lekin fuzz-bands cancel nahi hote — woh independent wobbles the. Toh ek tiny answer ab uss fuzz ke saath baitha hai jo pehle $a$ ke relative chhota tha lekin $r$ ke relative huge hai.

PICTURE. Do tall bars overlapping draw hain; unka difference upar ka patla sliver hai. Dono bars ka fuzz us sliver par pile ho jaata hai — visually error band sliver ka bada fraction hai.

Step 5 — Tiny answer se divide karna: amplifier appear hota hai

KYA HAI. Honest sawaal pucho: result ki relative error kitni buri hai? Bachi hui error ko true result $r = a - b$ se divide karo.

KYU. Relative error woh cheez hai jo batati hai kitne correct digits bache hain (dekho Round-off error propagation). Bade answer par badi absolute error theek hai; tiny answer par badi absolute error disaster hai. Tiny $r$ se divide karna hi woh jagah hai jahan explosion hoti hai.

PICTURE. Ek see-saw: numerator (fixed-size fuzz $∣ a ∣ + ∣ b ∣$ scale) ek taraf, denominator $∣ a - b ∣$ zero ki taraf shrink ho raha doosri taraf. Jaise jaise denominator collapse hota hai, ratio sky ki taraf shoot karta hai.

Step 6 — Ek worked collapse: dekho digits kaise marte hain

KYA HAI. Numbers daalo. $a = 200000.00001$ aur $b = 200000.0$ lo, toh true difference $r = 1 0^{- 5}$ hai.

KYU. Abstract $\infty$ convincing nahi hota; ek concrete digit count hoti hai. Hum amplification factor compute karte hain aur predict karte hain kitne digits bachenge.

PICTURE. Bar chart dikhata hai $16$ good digits andar jaate hain aur sirf kuch hi bahar aate hain, lost digits grey ho jaate hain.

Step 7 — Degenerate cases (kabhi koi gap mat chhodna)

KYA HAI. Formula ki har boundary sweep karo taaki koi scenario tumhe surprise na kare.

KYU. Ek smart 12-year-old se promise: tum kabhi aisa case nahi hit karoge jo maine nahi dikhaya. Yeh sab hain.

PICTURE. Char mini-panels, har case ke liye ek, har ek mein factor ki value likhi hai.

Definition

$\frac{∣ a ∣ + ∣ b ∣}{∣ a - b ∣}$ ke saare edge cases

$a = b$ exactly (panel 1): denominator $= 0$ , factor $= \infty$ . True result $0$ hai; har surviving digit galat ho sakta hai. Yeh total cancellation hai.
$a$ , $b$ far apart (panel 2): e.g. $a = 10$ , $b = 0.001$ . Denominator $\approx$ numerator, factor $\approx 1$ . Subtraction perfectly safe hai — koi cancellation nahi.
Opposite signs, $a > 0 > b$ (panel 3): ab $∣ a - b ∣ = ∣ a ∣ + ∣ b ∣$ , toh factor exactly $1$ hai. Positive se subtract karna... ruko — yeh actually magnitudes ka addition hai, aur same-sign magnitudes ka addition kabhi cancel nahi karta. Safe.
Ek input $0$ hai (panel 4): maan lo $b = 0$ . Factor $= ∣ a ∣/∣ a ∣ = 1$ . Cancel karne ke liye kuch nahi; result sirf $\overset{a}{^}$ hai, error $\sim u$ . Safe.

Rule yeh hai: danger ke liye same sign aur nearly equal magnitude chahiye. Koi bhi ek condition break karo aur tum safe ho.

Ek-picture summary

Yeh final figure saare saat steps compress karti hai: gappy number line → snap-to-dot with fuzz → do tall bars inherited fuzz ke saath → subtraction bars collapse karta hai lekin fuzz rakhta hai → sliver se division → amplification factor $\frac{∣ a ∣ + ∣ b ∣}{∣ a - b ∣}$ → digits lost.

Recall Feynman retelling — poora walkthrough plain words mein

Computer ki number line mein gaps hote hain, aur bade numbers ke liye gaps wider hote hain. Jab tum ek number likhte ho, woh nearest allowed dot par jump karta hai — woh chhota jump error hai, aur woh hamesha number ka lagbhag same tiny fraction hoti hai.

Ab do bade numbers lo jo almost same hain. Har ek already thoda jump kar chuka hai — aur kyunki woh bade hain, woh chhote jumps real terms mein chunky hain. Jab tum do bade numbers subtract karte ho, bade parts cancel ho jaate hain aur tum ek tiny answer ke saath reh jaate ho... lekin do chunky jumps abhi bhi wahan hain, uss tiny answer ke upar baaithe. Suddenly woh error, jo ek bade number ka chhota slice thi, ek chhote number ka huge slice ban jaati hai.

Yeh kitna bura hua yeh measure karne ke liye, leftover error ko tiny answer se divide karo. Kisi tiny cheez se divide karne par woh explode hoti hai. Exact "explosion factor" $\frac{∣ a ∣ + ∣ b ∣}{∣ a - b ∣}$ hai: upar badi cheezein, neeche tiny difference. Hamare example mein woh $4 \times 1 0^{10}$ hai, jo tumhare $16$ good digits mein se lagbhag $11$ kha jaata hai.

Escape hatch: twins ko subtract mat karo. Formula rewrite karo taaki near-equal subtraction kabhi ho hi nahi — jaise quadratic ke liye $x_{-} = c / (a x_{+})$ , ya $1 - cos x = 2 sin^{2} (x /2)$ . Subtraction kabhi galat nahi hoti; woh sirf uss damage ko reveal karti hai jo pehle se baked in thi. Toh uss route ke around jaao.

Recall

Recall Answers cover karo

$a - b$ mein error actually kahan se aati hai? ::: Yeh $\overset{a}{^}, \hat{b}$ store karne se inherit hoti hai; subtraction exact hai (Sterbenz) aur sirf use expose karti hai. $a$ aur $b$ subtract karne ka amplification factor kya hai? ::: $\frac{∣ a ∣ + ∣ b ∣}{∣ a - b ∣}$ . $a = 200000.00001$ , $b = 200000$ ke liye roughly kitne digits lost hote hain? ::: Lagbhag 11 (factor $\approx 4 \times 1 0^{10}$ hai, aur $lo g_{10} (4 \times 1 0^{10}) \approx 10.6$ ). Subtraction perfectly safe kab hoti hai? ::: Jab numbers ke opposite signs hoon, ya bahut different magnitudes hoon, ya ek zero ho — factor $1$ ke paas rehta hai. Kya float128 use karna catastrophic cancellation cure karta hai? ::: Nahi — yeh $u$ lower karta hai lekin amplification factor unchanged rehta hai; instead reformulate karo.