Skip to main content

Kahan 求和

Summary

Kahan 求和又称补偿求和或进位求和，用来降低有限精度浮点数序列累加时的舍入误差。浮点数位数有限，把一个很小的数加到很大的和上时低位会被截断丢失，朴素累加里这种误差会随项数不断累积，使总误差随 n 增长。Kahan 的做法是额外用一个补偿变量记录上一次因舍入丢失的低位部分，在下一次累加前先把它补偿回来，从而把总误差从与 n 相关压到接近常数级，代价只是每步多几次加减。给出用该补偿变量逐项累加的简短实现。

参考资料​

简介​

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

实现​

用一个变量 cc 累积每次加法因舍入而丢失的低位部分，在下一次累加前补偿回来，从而把总误差从与 nn 相关降到接近常数。

145 Bcpp
double kahan(vector<double> a)
{
	double res=0,c=0;
	for(auto x:a)
	{
		double y=x-c;
		double t=res+y;
		c=(t-res)-y;
		res=t;
	}
	return res;
}