6

在我的 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))

就像构建二叉树一样，但要在原地进行。排序应确保在每一步这两个加数具有可比性。

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

4

2 回答 2

10

解决此问题的标准方法之一是Kahan 求和算法。该算法将您的最坏情况错误减少到取决于您的浮点精度，而不是与向量的长度成比例增长（并且在 O(n) 时间内完成，尽管每次迭代需要更多计算）。

sumDoubles由于您对每个调用进行排序，Kahan summation 可能会优于您当前的求和，并且会另外提高pairwise summation的 O(log n) 到 O(1) 的错误增长。这就是说，如果sort不需要，成对求和可能会优于 Kahan 求和（由于涉及额外的每次迭代数学），而（对于您的情况）可能是最小的错误增长。

于 2013-10-02T04:56:37.787 回答
2

你应该按绝对值排序。目前，-100000000.0 在 0.000000001 之前排序。排序的想法是您可以添加相同大小的项。添加 -100000000.0 和 +100000000.0 如果完全没问题，那么它们应该排列在一起，但是添加 -100000000.0 和 0.000000001 会使您遇到准确性问题。

您的算法的第二个问题是您的评估顺序非常糟糕。正如您正确指出的那样，您有一个树结构，但即使如此，您也可以按任何顺序评估子表达式。内存访问的最有效顺序是添加 [0] 和 [1]，然后是 [2] 和 [3]，然后是 [0] 和 [2]，然后再添加 [4] 和 [5]。原因很简单：[0] 和 [2] 仍在缓存中，它们的值会发生变化。所以不要将中间值写回主存，只是为了以后读取和修改它们。（在树方面，这是 DFS 与 BFS 评估）

出于同样的缓存效率原因，我还将修改存储临时结果的位置。当然，将 [0] + [1] 存储在 [0] 中。但在那之后，[1] 就不再需要了。将 [2] + [3] 存储在 [1] 中。现在，再次添加 [0] 和 [1] 以获得 [0]..[3] 的总和 存储在 [0] 中。

总结：尽快将中间结果加在一起，减少中间结果的数量，并将它们存储在数组开头的连续内存中，而不是分散在各处。

于 2013-10-02T07:59:44.853 回答