algorithm - float 的精确和

Question

我知道 a similar question ，但我想征求人们对我的算法的意见，即以实际成本尽可能准确地对 float 求和。

这是我的第一个解决方案:

put all numbers into a min-absolute-heap. // EDIT as told by comments below
pop the 2 smallest ones.
add them.
put the result back into the heap.
continue until there is only 1 number in the heap.

这个需要 O(n*logn) 而不是正常的 O(n)。这真的值得吗？

第二种解决方案来 self 正在处理的数据的特性。这是一个巨大的正数列表，数量级相似。

a[size]; // contains numbers, start at index 0
for(step = 1; step < size; step<<=1)
    for(i = step-1; i+step<size; i+=2*step)
        a[i+step] += a[i];
    if(i < size-1)
        a[size-1] += a[i];

基本思想是以“二叉树”方式求和。

注意:这是一个伪 C 代码。 step<<=1表示乘以 2。这个需要 O(n)。我觉得可能有更好的方法。你能推荐/批评吗？

Answer 1

Kahan's summation algorithm比直接求和要精确得多，并且它在 O(n) 中运行(比直接求和慢 1-4 倍，这取决于 float 与数据访问的速度相比。在桌面硬件上肯定慢不到 4 倍，并且没有任何数据改组)。

---

或者，如果您使用的是通常的 x86 硬件，并且您的编译器允许访问 80 位 long double 类型，只需使用简单的求和算法和 类型的累加器长双。仅在最后将结果转换为 double。

---

如果你确实需要很高的精度，你可以通过对变量c、y使用long double来组合以上两种解决方案， t, Kahan求和算法中的sum。