又一个小知识

Kahan求和

Kahan 求和算法，又名补偿求和或进位求和算法，是一个用来降低有限精度浮点数序列累加值误差的算法

思路

计算机的浮点数误差有时候会导致很多问题，如下面

double x;
...
if (x < 0)
    x = -x;
else
    cout << x << endl;

这样写是错误的，首先，比较浮点数最好写成函数，即 cmp(x, 0) < 0 ，其次，那个 else 也并非代表了 x >= 0 ，因为 $x$ 可能为 $NaN$ （not a number）

又比如，浮点数满足交换律，即 $a + b = b + a$ ，但不满足结合律即 $a + (b + c) \ne (a + b) + c$

由于浮点数的种种误差，在只加几个数的时候还可以接受，但如果要把很多浮点数连加，在一些题目里面误差就无法接受了

William Kahan提出一种解决方法：用一个额外的浮点数记录误差，最后修正

具体地，如果现在正在加 $a$ ，而已有的和为 $sum_{old}$ ，则先计算 $sum_{now} = sum_{old} + a$ ，而误差用 $c$ 记录，跟新为 $c = c + (a - (sum_{now} - sum_{old}))$

代码

double kahan(double x[], int len)
{
    double sum = 0, c = 0;
    for (int i = 1; i <= len; ++i)
    {
        double y = x[i] - c; //先补上前面误差
        double t = sum + y;
        c = (t - sum) - y; //跟新误差
        sum = t;
    }
    return sum;
}