浮点数precise总和 [英] Precise sum of floating point numbers

问题描述

我知道<一个href="http://stackoverflow.com/questions/5257166/java-floats-and-doubles-how-to-avoid-that-0-0-0-1-0-1-0-9000001">a类似的问题，但我要问的人的意见对我的算法总结浮点数尽可能准确地与实际成本。

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 $ C $℃。 步骤LT;＆LT; = 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的的总和算法是显著更precise比简单的求和，而且它在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位长双键入，只需使用简单的求和算法与类型的蓄电池长双。只有结果转换为双在最后。

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.

如果你真的需要大量的precision，您可以通过使用长双变量 C ，是， T ，之在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.

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