---
# System prepended metadata

title: Kahan Sum 簡單解釋

---

> 如果 （大數＋小數）不會是精確值，那麼（計算結果 - 大數）就不會剛好等於小數，這兩者之間的差就是被捨棄掉的誤差。

雖然它並不能解決單一次的精度損失，但它可以透過把每次的損失加在一起，直到湊夠了下次能感知的最小步長，就可以把它加回去了。

舉個例子。

```c
int main() {
    float big = 16777216;
    float small = 1;

    for (int i = 0; i < 13; i++) {
        big += small;
    }

    printf("%f", big);
}
```

預期結果應該是16,777,229，但結果，欸！居然還是原來的數值 16,777,216！為什麼會這樣？這是因為在 2^24 = 16,777,216 以後，最小步長要為 2 才能成功加總。所以才會導致上述迴圈一直在原地踏步。

我是怎麼知道的呢？首先要從 float 的 bit pattern 推出表示的值，可以靠以下公式。
![DataRep_Float](https://hackmd.io/_uploads/r1KL3hsrxl.png)

$$
\text{float} = (-1)^s \times 2^{e-127} \times \frac{2^{23} + f}{2^{23}}
$$

而你可以簡化成

$$
(-1)^s \times (2^{e-127} + 2^{e-150} \times f)
$$

從這裡可以看出，在 $e \geq 151$ 之後，就沒有辦法再表示出每個整數。因為當我代入 $e = 151$，$2 \times f$ 就會導致每次 $f$ 的增加都會被迫乘以 2，也就是我們說的最小步長變為 2。

[TODO]: 寫一篇詳細講解 bit pattern of floating-point 的文章。

我們把迴圈換成 Kahan Sum。
```c
int main() {
    float big = 16777216;
    float small = 1;

    float c = 0.0f;
    for (int i = 0; i < 13; i++) {
        float y = small - c;
        float temp = big + y; // 大數加小數不等於精確值
        c = (temp - big) - y; // temp 先減大數，使步長 < 1
                              // 再減掉小數，取得精度損失。
        big = temp;
        // 下一次加總，我們把精度損失加到小數上(y)，使它的步長增加。
        // 步長不夠則繼續，若夠了 c 將會恢復到 0.0f。
    }

    printf("%f", big);
}
```
結果會是 16,777,228，雖然不是精確值16,777,229，但至少不再原地踏步了！這就是因為我們把每次的損失集合起來，等到下次步長夠了以後，再把它加回去。雖然還是不精確，但至少不再原地踏步了。