Compensated Summation/Kahan‘s Summation的理解
阅读《Efficient Generation of Error-Inducing Floating-Point Inputs via Symbolic Execution》这篇论文时,文中提到的Commpensated Summation没看太懂,代码如下:
查阅资料发现Compensated Summation也叫Kahan’s Summation,该算法的主要思想就是记录每次加法操作引入的误差项,然后在下次操作中补回去,从而减少误差的积累效应。
借鉴:https://blog.csdn.net/SlowIsFastLemon/article/details/103386679
按自己的理解重新实现该算法:
sum = 0
delta = 0 // 记录误差项
for i in range(100000):
real_num = 0.1;
num = real_num + delta; // 加和值=本次要加的值+上次精度损失,由于精度丢失,这里的delta小于零,故减去一个负数相当于加上一个正数
temp = sum + num // 计算本次求和结果
delta = temp - sum - num // 计算本次求和带来的精度损失,更新delta
sum = temp // 更新sum