添加多个浮点变量时最大程度地减少浮点错误 [英] Minimize floating point error when adding multiple floating point variables

问题描述

在我的c ++应用程序中，我有一个范围为(0,1)的双精度向量，并且我必须尽可能准确地计算其总数. 感觉应该早已解决此问题，但我找不到任何东西.

In my c++ app i have a vector of doubles in the range (0,1) and i have to calculate its total as accurately as possible. It feels like this issue should have been addressed before, but i cant find anything.

显然，如果向量大小很大并且某些项的大小显着小于其他项，那么迭代向量中的每个项并执行sum + = vect [i]会累积明显的误差.

Obviously iterating through each item on the vector and doing sum+=vect[i] accumulates a significant error if the vector size is large and there are items which are significantly smaller then the others.

我当前的解决方案是此功能:

My current solution is this function:

double sumDoubles(vector<double> arg)// pass by copy
{
  sort(arg.rbegin(),arg.rend());  // sort in reverse order
  for(int i=1;i<=arg.size();i*=2)
    for(int j=0;j<arg.size()-i;j+=(2*i))
        arg[j]+=arg[j+i];
  return arg[0];
}

基本上，它以升序对输入进行排序并计算成对和:

Basically it sorts the input in ascending order and calculates pairwise sums:

a + b + c + d + e + f + g + h =(((a + b)+(c + d))+((e + f)+(g + h))

a+b+c+d+e+f+g+h=((a+b)+(c+d))+((e+f)+(g+h))

就像构造一个二叉树一样，但是要就地进行.排序应确保两个步骤的每一步都具有可比较的大小.

Like constructing a binary tree, but doing it in place. Sorting should ensure that at each step the two summands are of comparable magnitude.

上面的代码确实比具有累加总和的单循环执行得更好. 但是我很好奇是否可以进一步提高精度而又不降低性能.

The code above does perform better than a single loop with accumulative sum. However i am curious if it is possible to increase precision further while not degrading performance too much.

推荐答案

解决此问题的标准方法之一是 Kahan sumsum算法.该算法将最坏情况的误差减少到取决于浮点精度，而不是与向量的长度成比例地增加(并且以O(n)的时间来完成，尽管每次迭代都会进行更多的计算).

One of the standard ways of approaching this issue is the Kahan summation algorithm. This algorithm reduces your worst-case error to being dependent upon your floating point precision rather than growing proportional to the length of your vector (and does it in O(n) time, albeit with more calculations per iteration).

由于您对每个呼叫进行排序，Kahan求和可能会胜过您当前的sumDoubles，并且还会进一步改善成对求和从O(log n)到O(1)的误差增长.这就是说，如果sort是不必要的，则成对求和(由于所涉及的附加的逐项迭代数学)可能会以(对于您的情况)最小的误差增长优于Kahan求和.

Kahan summation will likely outperform your current sumDoubles due to your sorting every call, and will additionally improve pairwise summation's error growth of O(log n) to O(1). This said, if the sort is unnecessary, pairwise summation will likely outperform Kahan summation (due to the additional per-iteration math involved) with what may be (for your circumstances) minimal error growth.

这篇关于添加多个浮点变量时最大程度地减少浮点错误的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！