c++ - 添加多个浮点变量时最小化浮点错误

Question

在我的 C++ 应用程序中，我有一个范围为 (0,1) 的 double vector ，我必须尽可能准确地计算它的总数。感觉这个问题之前应该已经解决了，但是我找不到任何东西。

显然，如果 vector 大小很大并且有些项明显小于其他项，则迭代 vector 上的每个项并执行 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 summation algorithm .该算法将最坏情况的错误减少为取决于浮点精度，而不是与 vector 的长度成比例增长(并且在 O(n) 时间内完成，尽管每次迭代计算更多)。

Kahan 总和可能会优于您当前的 sumDoubles，因为您对每个调用都进行了排序，并且还会进一步改进 pairwise summation的 O(log n) 到 O(1) 的错误增长。这就是说，如果 sort 是不必要的，成对求和可能会优于 Kahan 求和(由于涉及额外的每次迭代数学)，并且(对于您的情况)可能是最小的错误增长。