添加多个浮点变量时,最大限度地减少浮点错误

Question

在我的c ++应用程序中,我有一个范围(0,1)的双精度矢量,我必须尽可能准确地计算它的总和.感觉这个问题应该先解决,但我找不到任何东西.

显然迭代矢量上的每个项目并且如果矢量大小很大并且有些项目明显小于其他项目,则执行sum + = vect [i]会累积一个重大错误.

我目前的解决方案是这个功能:

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

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

A + B + C + d + E + F + G + H =((A + B)+(C + d))+((E + F)+(G + H))

就像构建二叉树一样,但要做到位.排序应确保在每个步骤中两个加数的大小相当.

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

Answer 1

解决这个问题的标准方法之一是Kahan求和算法.该算法将您的最坏情况误差降低为依赖于您的浮点精度,而不是与矢量长度成比例增长(并且在O(n)时间内完成,尽管每次迭代计算的次数更多).

sumDoubles由于您对每次调用进行排序,Kahan求和可能会超过您的当前值,并且还会改善O(log n)到O(1)的成对求和的误差增长.这就是说,如果sort没有必要,成对求和可能会胜过Kahan求和(由于涉及额外的每次迭代数学),可能(对于您的情况)最小误差增长.