Kahan 求和算法(Kahan Summation)

Kahan 求和算法(Kahan Summation Algorithm),又称补偿求和,是一种用于提高浮点数序列求和精度的数值算法。它由计算机科学家 William Kahan 提出,通过跟踪并补偿每次加法中因舍入而丢失的低位比特,大幅减小大规模浮点累加的误差累积。

概述

浮点数用有限位表示,直接顺序累加时,当一个较大的部分和与一个较小的加数相加,较小数的低位会被舍入丢弃,误差随累加次数不断积累。朴素求和的误差上界与项数成正比,在数据量大或数值量级悬殊时尤为明显。Kahan 求和引入一个补偿项,把丢失的部分保存下来在后续补回,从而把误差控制在与项数几乎无关的水平。

核心原理

• 维护两个变量:累加和 sum 与补偿量 c,c 初始为零,记录上一次运算被舍掉的低位。
• 每加入一个新数时,先用该数减去补偿量得到修正后的加数。
• 把修正后的加数加到 sum 上得到新的和,再通过新和与旧和之差,反推出这次实际吸收了多少,与修正加数比较,更新补偿量 c。
• 如此循环,c 始终携带被舍去的高精度残差,使总误差不随项数线性增长。

需要注意实现时不能被编译器的激进浮点优化重排,否则补偿步骤会被抵消而失效。

应用场景

Kahan 求和常用于科学计算、数值积分、统计量计算、机器学习中大批量数据的均值与方差计算等对精度敏感的场景。当需要对海量浮点数据求和、又不希望改用更慢的高精度类型时,它是一种低成本的精度改进方案。

常见问题

问:它能完全消除浮点误差吗?答:不能。它只是显著减小累积误差,把误差从与项数成正比降到接近常数级,但单次运算本身的舍入误差仍然存在。

问:为什么有时它似乎没生效?答:常见原因是编译器在高优化等级下对浮点表达式重排,把补偿步骤化简掉。应使用限制此类优化的编译选项,或采用不易被优化掉的等价写法。