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