浮点数的精确总和 [英] Precise sum of floating point numbers

问题描述

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

I am aware of a similar question, but I want to ask for people opinion on my algorithm to sum floating point numbers as accurately as possible with practical costs.

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

Here is my first solution:

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

This one would take O(n*logn) instead of normal O(n). Is that really worth it?

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

The second solution comes from the characteristic of the data I'm working on. It is a huge list of positive numbers with similar order of magnitude.

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];

基本思想是以二叉树"方式求和.

The basic idea is to do sum in a 'binary tree' fashion.

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

Note: it's a pseudo C code. step<<=1 means multiply step by 2. This one would take O(n). I feel like there might be a better approach. Can you recommend/criticize?

推荐答案

Kahan 求和算法 是比直接求和更精确，并且它在 O(n) 中运行(比直接求和慢 1-4 倍，具体取决于浮点与数据访问相比的速度.在桌面硬件上肯定慢不到 4 倍，并且没有任何数据的改组).

Kahan's summation algorithm is significantly more precise than straightforward summation, and it runs in O(n) (somewhere between 1-4 times slower than straightforward summation depending how fast floating-point is compared to data access. Definitely less than 4 times slower on desktop hardware, and without any shuffling around of data).

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

Alternately, if you are using the usual x86 hardware, and if your compiler allows access to the 80-bit long double type, simply use the straightforward summation algorithm with the accumulator of type long double. Only convert the result to double at the very end.

如果你真的需要很高的精度，可以结合以上两种方案，对变量c、y使用long double，t, sum 在 Kahan 的求和算法中.

If you really need a lot of precision, you can combine the above two solutions by using long double for variables c, y, t, sum in Kahan's summation algorithm.

这篇关于浮点数的精确总和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！