将大量小浮点数添加到一起的好方法是什么？

Question

假设您在一个数组中有100000000个32位浮点值,并且每个浮点数的值都在0.0到1.0之间.如果你试图将它们全部加起来像这样

result = 0.0;
for (i = 0; i < 100000000; i++) {
    result += array[i];
}

你遇到的问题result远远大于1.0.

那么有哪些方法可以更准确地执行求和？

Answer 1

听起来你想要使用Kahan Summation.

根据维基百科,

的Kahan的求和算法(也称为补偿求和)显著降低通过添加有限精度浮点数的一个序列获得的总的数值误差,相对于明显的方法.这是通过保持单独的运行补偿(一个变量来累积小错误)来完成的.

在伪代码中,算法是:

function kahanSum(input)
 var sum = input[1]
 var c = 0.0          //A running compensation for lost low-order bits.
 for i = 2 to input.length
  y = input[i] - c    //So far, so good: c is zero.
  t = sum + y         //Alas, sum is big, y small, so low-order digits of y are lost.
  c = (t - sum) - y   //(t - sum) recovers the high-order part of y; subtracting y recovers -(low part of y)
  sum = t             //Algebraically, c should always be zero. Beware eagerly optimising compilers!
 next i               //Next time around, the lost low part will be added to y in a fresh attempt.
return sum