在我的 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))
就像构建二叉树一样,但是要原地进行。排序应确保在每一步中两个被加数的大小相当。
上面的代码确实比具有累加和的单个循环执行得更好。 不过,我很好奇是否有可能在不过度降低性能的情况下进一步提高精度。
最佳答案
解决此问题的标准方法之一是 Kahan summation algorithm .该算法将最坏情况的错误减少为取决于浮点精度,而不是与 vector 的长度成比例增长(并且在 O(n) 时间内完成,尽管每次迭代计算更多)。
Kahan 总和可能会优于您当前的 sumDoubles
,因为您对每个调用都进行了排序,并且还会进一步改进 pairwise summation的 O(log n) 到 O(1) 的错误增长。这就是说,如果 sort
是不必要的,成对求和可能会优于 Kahan 求和(由于涉及额外的每次迭代数学),并且(对于您的情况)可能是最小的错误增长。
关于c++ - 添加多个浮点变量时最小化浮点错误,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/19130042/