Floating point gotchas — catastrophic cancellation, associativity failure: Foundations

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

Yeh page kuch bhi assume nahi karta. Parent note Floating Point Gotchas ko touch karne se pehle, hum har woh symbol build karte hain jo woh use karta hai, ek ek brick karke, har brick pichli wali ke upar.

0. Computer ke liye "number" hota kya hai?

Ek calculator screen ki fixed width hoti hai. Agar woh 4 digits dikha sakti hai, toh $12340000$ fit hota hai ( $1.234 \times 1 0^{7}$ ke roop mein) lekin $1$ add karne se kuch nahi badlta — woh $1$ right edge se gir jaata hai. Ek real computer bhi yahi idea hai, bas zyaada digits ke saath. Neeche sab kuch "digits edge se gir jaati hain" ka precise version hai.

Figure — Floating point gotchas — catastrophic cancellation, associativity failure

1. Bits, base-2, aur mantissa

Ek bit ek single 0 ya 1 hota hai. Computers numbers ko base 2 (binary) mein likhte hain, bilkul waise hi jaise hum base 10 mein likhte hain — lekin place-values $10$ ki nahi, $2$ ki powers hoti hain.

Base 10 mein, $3.14 = 3 + \frac{1}{10} + \frac{4}{100}$ . Base 2 mein, $(1.011)_{2} = 1 + 0 \cdot \frac{1}{2} + 1 \cdot \frac{1}{4} + 1 \cdot \frac{1}{8} = 1.375$ .

Aise kyun split karte hain? Kyunki yeh binary mein scientific notation hai. "Digits" aur "scale" ko alag store karna memory ke ek chhote hisse ko $1 0^{- 300}$ aur $1 0^{+ 300}$ dono represent karne deta hai. Topic ke liye yeh zaroori hai kyunki exponent gap ka size decide karta hai — aur gap size hi poori kahani hai.

2. Gap, aur machine epsilon $ε_{mach}$

Kyunki mantissa mein sirf 52 bits hain, number $1.0$ ke paas sabse chhoti change jo tum kar sakte ho woh last bit ko flip karna hai, jo $2^{- 52}$ worth hai. $1.0$ ke baad gap ka size yahi hai.

Yeh picture ek crucial fact dikhati hai: gap number ki magnitude ke saath badhti hai. $1$ ke paas gap $\approx 2.2 \times 1 0^{- 16}$ hai; $1 0^{16}$ ke paas gap lagbhag $2$ hai; $1 0^{16}$ ke paas number $1$ ek gap se bhi chhota hai aur add karne par simply gaayab ho jaata hai. Yeh akela visual parent ka " $1 + 1 0^{16} = 1 0^{16}$ " absorption explain karta hai.

3. Relative vs absolute error — do rulers

Dono kyun? $x = 2$ ke liye $1$ se galat hona disastrous hai (50%) lekin $x = 1 0^{9}$ ke liye negligible (billionth part). Computer ki guarantee relative ruler mein batayi jaati hai kyunki woh saari magnitudes mein constant rehti hai.

Symbols kaise padhein:

$fl (x)$ ::: " $x$ ka float" — $x$ ke sabse kareeb representable double.
$δ$ (delta) ::: woh tiny relative fudge, $[- u, + u]$ mein kahin bhi.
$u = \frac{1}{2} ε_{mach} \approx 1.1 \times 1 0^{- 16}$ ::: kyunki rounding kareeb wala neighbour choose karta hai, tum kabhi bhi aadhi gap se zyaada galat nahi ho sakte.

Parent note jo bhi derive karta hai — cancellation amplifier, summation bound — sab is ek line par lagaya gaya algebra hai.

4. Symbols jo parent note mein milenge

5. Yeh bricks topic kaise banate hain

Ise top-down padhte hain: raw bits format dete hain, format gap deta hai, gap $ε_{mach}$ deta hai, aur relative/absolute distinction ke saath milke rounding model milta hai — woh single equation jisse Catastrophic cancellation, Round-off error propagation, Kahan compensated summation aur Quadratic formula numerical issues sab follow karte hain. Poori chain Numerical stability and conditioning mein land hoti hai.

Equipment checklist

Tum parent note ke liye ready ho jab bina deekhe har sawaal ka jawaab de sako:

(1.101)_{2}

ko decimal mein convert karo.

1 + \frac{1}{2} + \frac{1}{8} = 1.625

IEEE-754 double kitne mantissa bits store karta hai?

52 (plus ek hidden leading 1 = 53 bits of precision).

ε_{mach}

kya hai aur yeh kya measure karta hai?

2^{- 52} \approx 2.22 \times 1 0^{- 16}

1.0

aur next double ke beech ka relative gap.

Stored

\overset{x}{^}

of true

x

ke liye absolute vs relative error — dono define karo.

absolute

= ∣ \overset{x}{^} - x ∣

; relative

= ∣ \overset{x}{^} - x ∣/∣ x ∣

Rounding model batao aur har symbol ka matlab batao.

fl (x) = x (1 + δ)

∣ δ ∣ \leq u = \frac{1}{2} ε_{mach}

;

fl

= round to nearest double,

δ

= relative slip,

u

= half-gap max.

Bade numbers ke liye representable numbers ke beech ki gap kyun badhti hai?

exponent poori mantissa ko scale karta hai, toh last-bit step

2^{e - 52}

e

ke saath badhta hai.

Computer ki guarantee relative error mein kyun batayi jaati hai?

kyunki yeh saari magnitudes mein constant rehti hai, absolute error ke unlike.