algorithm - 将大量小花车加在一起有什么好方法？

Question

假设您在一个数组中有 100000000 个 32 位浮点值，并且每个 float 的值都在 0.0 到 1.0 之间。如果你试图像这样总结它们

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

当 result 变得比 1.0 大得多时，您会遇到问题。

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

Answer 1

听起来您想使用 Kahan Summation .

根据维基百科，

The Kahan summation algorithm (also known as compensated summation) significantly reduces the numerical error in the total obtained by adding a sequence of finite precision floating point numbers, compared to the obvious approach. This is done by keeping a separate running compensation (a variable to accumulate small errors).

In pseudocode, the algorithm is:

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