浮点数的精确总和

Question

我知道一个类似的问题,但我想请求人们对我的算法的意见,以尽可能准确地将浮点数与实际成本相加.

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

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).这真的值得吗？

第二个解决方案来自我正在研究的数据的特征.这是一个巨大的正数列表,具有相似的数量级.

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的求和算法比直接求和要精确得多,并且它在O(n)中运行(比直接求和慢1-4倍,这取决于浮点与数据访问的比较速度.桌面上的速度肯定少于4倍硬件,没有任何数据混乱).

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

如果你真的需要大量的精密,您可以通过使用结合上述两种解决方案long double变量c,y,t,sum在Kahan的的总和算法.

Answer 2

如果您担心减少求和中的数值误差,那么您可能对Kahan的算法感兴趣.