Kahan 補償求和
/ KAH-han /
把一長串數字相加似乎是世上最安全的事，然而它卻是經典的流失準確度之道。每當你把一個新項加到一個很大的累計總和上，那次加法的低位小位元就被捨掉、丟棄；歷經一百萬次加法，這些丟棄的碎屑會堆積成真實的誤差。以 William Kahan 命名的 Kahan 補償求和，是一個巧妙的修正，它接住碎屑並把它們回饋進去。
其想法是保留第二個變數 c，用來記住上一步丟失的捨入誤差，並在加入下一項之前把它加回來。迴圈如下：對每個 x，令 y = x - c（用累積的補償修正此項）；令 t = sum + y（捨入後的新總和）；令 c = (t - sum) - y（精確復原 y 中有多少被捨入丟失）；再令 sum = t。相減 (t - sum) - y 是精確的，並隔離出那些被丟棄的低位位元，由 c 帶往下一次加法。它每項只多花三個廉價運算，且幾乎不耗額外記憶體。
回報相當可觀：n 項的天真循序求和，最壞相對誤差按 n*u 成長，而 Kahan 求和的誤差大致以 2u 加上一個與 n 無關的微小項為界——本質上彷彿你以高得多的精度求和。每當你要把許多同號、同量級的值相加（平均、內積、數值積分、物理時間步進）時，它都是標準工具。兩點誠實的告誡：一個激進最佳化的編譯器可能假設實數代數而把 c 「化簡」為零，所以這技巧可能需要保護（volatile，或一個關閉 fast-math 的旗標）；而遞迴拆分總和的成對求和（pairwise summation）能以更低成本達到類似的 O(log n)*u 界限，許多函式庫實際上用的正是它。
把值 0.1 相加一千萬次。在雙精度中的天真求和會累積出可見的誤差（結果會偏離真值 1000000.0 約 1e-3 之譜），因為每個 0.1 都不精確，丟失的位元層層複利。Kahan 求和則回傳達到完整雙精度準確度的 1000000.0，復原了天真求和悄悄丟失的那些數字。
補償變數 c 重新捕捉每一步丟失的低位位元。
Kahan 求和正是仰賴「浮點不是實數運算」這個事實；一個「知道」(t - sum) - y 必等於 0 的最佳化器會把補償刪掉。要保護它，或改用編譯器無法錯誤化簡的成對求和。