浮點數與數值考量 練習題 (Practice - Floating-Point Data Representation)

三欄位：Sign (S)、Exponent (E)、Mantissa (M)。公式 value = (-1)^S × 1.M × 2^(E - bias)，bias = 2^(e-1) - 1。分工：E 決定動態範圍 (range) (E 位數越多範圍越廣)、M 決定精度 (precision) (M 多 1 bit → 最大表示誤差減半)、S 只管正負號 (S=0 正、S=1 負)。

1.M 限制讓每個浮點數的位元樣式唯一 (例如 0.5D 只能寫成 1.0B × 2^-1，0.1B × 2^0 與 10.0B × 2^-2 都不合法)。因為尾數一定是 1.XX，前導的 1. 是隱含、不必存的，所以 2-bit 尾數實際攜帶 3-bit 資訊。一般規則：IEEE 的 m-bit 尾數等效於 (m+1)-bit 尾數，省下的這 1 bit 是免費的精度。

bias = 2^(e-1) - 1 (e = 指數位元數)；3-bit → bias 2^2 - 1 = 3 (excess-3)，把它加到指數的 two's complement 上。核心優點：excess code 隨真實值單調遞增，所以能用便宜的 unsigned comparator 直接比較有號指數 (例如 001(−2) < 100(1) 直接成立)，無號比較器比 signed 更小更快。全 1 樣式 (111) 被保留作特殊用途。

Exponent bits 定義主要區間 (major intervals) — 區間落在相鄰 2 的次方之間；Mantissa bits 定義每區間的代表數個數 = 2^N (N = mantissa 位數)，因此決定 precision。每往 0 移動一個區間寬度減半 (4 → 2 → 1 → 0.5…)，但每區間固定 2^N 個代表數，所以絕對值越小代表數越密、表示越精確。例外：normalized 1.M 排除 0，導致緊鄰 0 反而出現空洞。

Abrupt underflow：只要 E=0 就一律當作 0 → 0 可表示，但 0 到 1.0 之間全變 0，空洞反而更大。Denormalization (IEEE 採用)：E=0 時尾數改解讀為 0.M、指數固定沿用上一區間值，把最後一區間的代表數攤開均勻填平空洞 (公式 value = (-1)^S × 0.M × 2^(2 - 2^(n-1)))。代價：硬體偵測 + 切換成本高 (可達數千 cycle)，故早期 CUDA 不支援；cc 1.3+ 支援 denorm double、cc 2.0+ 支援 denorm single。

特殊樣式：E 全 1 + M≠0 → NaN；E 全 1 + M=0 → (-1)^S × ∞；E 全 0 + M≠0 → denormalized；E 全 0 + M=0 → 0。配置：single = 1/8/23 (bias 127)，double = 1/11/52 (bias 1023)。double 的 mantissa 多 29 bits → 最大表示誤差降為 single 的 1/2^29，且多 3 個 exponent bit → 動態範圍更廣。

Signaling NaN (mantissa MSB = 0)：作為運算輸入時觸發 exception，用於標記未初始化資料 / mission-critical 中斷。Quiet NaN (mantissa MSB = 1)：運算後產生另一個 quiet NaN、不中斷，印成 "NaN" 供事後檢視。目前 GPU 硬體不支援 signaling NaN (大規模平行下難以精確 signaling)。∞ 由 overflow 產生 (如大數 ÷ 極小數)，任何代表數 ÷ ±∞ = 0；NaN 由 0/0、0×∞、∞/∞、∞−∞ 等無意義運算產生。

Precision 由 mantissa 位數決定 (靜態的最大表示誤差，多 1 bit 減半)；Accuracy 由執行的運算決定 (動態，看運算如何實作)，最常見誤差來源是 rounding。ULP (Units in the Last Place) = mantissa 最低位的位權，是衡量運算誤差的單位。正確捨入的 add/sub ≤ 0.5 ULP (今日所有 CUDA device 達此)。除法與超越函數 (sin、1/x) 多用 polynomial approximation 實作，項數不足時誤差可 > 0.5 ULP (早期 inversion 達 2 ULP)。

Numerically stable = 只要解存在，演算法對任意輸入都能找到合適的運算順序並求得解；做不到的稱 unstable。naive Gaussian elimination 在某一步若lead 變數係數為 0 (例如第一式 0X + 5Y + 2Z = 16) 就無法用該係數做 division 來消元而失敗，但該系統其實可解 → 屬 unstable。修正方法是 pivoting：在剩餘方程式中找出 lead 變數係數不為 0 (實務上選絕對值最大) 的一式，與最上方的式子 swap row 後再繼續消元。

每個 thread 負責矩陣的一個 row；若系統可放進 shared memory 就用一個 thread block 處理。所有 thread 迭代各 step：pivot row 做 division (除以 lead 係數正規化) → barrier (__syncthreads) → 下方各 row 做 subtraction (減去 pivot row 以消元) → barrier。每完成一欄，負責該 row 的 thread 在回代前已無工作 → 停止參與，其餘 thread 繼續。變數越多，平行加速越顯著。

先正規化：0.5D = 1.0B × 2^-1。

• S = 0 (正)。
• 指數真值 = −1 → excess-3 code = -1 + 3 = 2 = 010B，故 E = 010。
• 尾數 1.00 去掉隱含 1. → M = 00。

拼起來：0 | 010 | 00 = 001000B。

兩數指數差 = 3，較小者尾數右移 3 位對齊：1.00B × 2^-2 → 0.001B × 2^1。相加：1.00B × 2^1 + 0.001B × 2^1 = 1.001B × 2^1。此理想結果需 3 個 mantissa bit，但格式只有 2 → 必須 round 到 1.01B × 2^1 或 1.00B × 2^1。引入誤差 = 0.001B × 2^1 = 最低位權的一半 = 0.5 ULP (正確捨入的上限)。

(a) round-to-zero 是截斷而非取最近，誤差可達幾乎整個最低位權 → 最大 ≈ 1 ULP (相對正確捨入的 0.5 ULP 差一倍)。
(b) 9 cycle × 2 bit = 18 個正確 significant bit (含隱含 1.)。single 共有 24 個 significant bit (1 隱含 + 23 mantissa)，故有 24 − 18 = 6 個最低位 mantissa bit 被補 0。最大誤差出現在這 6 bit 真值全為 1：2^-18 + … + 2^-23 = 63 × 2^-23 → ≈ 63 ULP (約 2^6 = 64 ULP)。

循序：(((1+1)+0.25)+0.25)，每加一個 0.25 時對齊右移後超出 2-bit mantissa 範圍被吞掉 (swamping) → 得 2 (誤差 0.5)。平行 tree：(1+1) + (0.25+0.25) = 2 + 0.5 = 2.5 (精確)，因為兩個小數先合併成 0.5 才夠大不被吞。成因：浮點加法不滿足結合律，(a+b)+c ≠ a+(b+c)。啟示：此例平行較準只是巧合，也能構造平行更不準的情境，不可假設「平行=更準」。改善技巧：presort 升冪 + 大小相近分組 (讓同組數量級接近、循序由小到大累積)、進階用 Kahan compensated summation。注意排序方向要配合分組策略 (習題 4：已排序陣列若把最小最大配對在同一子樹反而更差)。

單 block / shared memory：所有係數都在 shared memory，可直接跑 parallel max reduction 找絕對值最大的 lead 係數，只要控制 warp 內 control divergence 即可，成本可接受。跨多 block / 多 cluster node：係數分散在不同 block / node，pivoting 需做全域檢查 (global inspection)，跨 node 通訊極昂貴 → 這正是 communication-avoiding algorithms 的動機。兩種對策：Partial pivoting — 把候選 swap 限制在局部方程式集合 (限制全域檢查成本)，代價是可能略降數值準確度；Randomization — 隨機化處理，研究顯示仍能維持高準確度。本質是用一點點準確度 / 隨機性換取避免昂貴的全域資料檢查。

核心心法：浮點數的世界裡，precision (能表示多細) 與 accuracy (算出來多準) 是兩回事 — 前者看 mantissa 位數、後者看運算順序與硬體實作。對平行程式設計師而言最關鍵的啟示是：結合律對浮點不成立，所以平行 reduction、Gaussian elimination 等改變運算順序的演算法可能改變結果準確度甚至成敗，需靠排序、分組、Kahan 加總、pivoting 與 communication-avoiding 等技巧來權衡準確度與效能。