卡韓求和算法

在數值分析中，卡韓求和算法（英語：Kahan summation algorithm），又稱補償求和（compensated summation），嚴格來說，補償求和還有其他變體：參見  是一種能顯著減少將有限精度的浮點數數列相加時產生的之算法。與簡單的累加法相比，該算法透過維護一個獨立的「運行補償量」（用於累積小誤差的變數）來運作，實際上是利用補償變數的精度來擴展求和結果的精度。特別是對於  個數的序列求和，直接累加在最壞情況下的誤差隨  線性增長；而對於隨機輸入，由於捨入誤差形成隨機遊走，其均方根誤差隨  增長。. 若使用補償求和且補償變數具有足夠精度，其最壞情況下的誤差界限實際上與  無關，因此可以對大量數值求和，而誤差僅取決於結果的浮點精度。該演算法歸功於威廉·卡韓；. 似乎也獨立提出了類似的算法（因此也被稱為卡韓－巴布什卡求和）。Babuska, I.: Numerical stability in mathematical analysis. Inf. Proc. ˇ 68, 11–23 (1969) 早期類似的技術還包括：例如布雷森漢姆直線演算法，它在整數運算中追蹤累積的誤差（儘管首度記錄於相近時間），以及ΔΣ調變。
 演算法 
該演算法的虛擬碼如下：

 function KahanSum(input)
     // 初始化累加器
     var sum = 0.0
     // 遺失低位元的運行補償量
     var c = 0.0
     // 陣列 input 的索引從 1 到 input.length
     for i = 1 to input.length do
         // y 為本次待加項減去上一次累積的補償
         var y = input[i] - c
         // 當 sum 很大且 y 很小時，y 的低位數字會遺失
         var t = sum + y
         // (t - sum) 抵銷了 y 的高位部分
         // 再減去 y 即可找回負的「遺失位元」
         c = (t - sum) - y
         sum = t
     next i

 return sum
Category:計算機算術
Category:数值分析