假设我们在c++中有一个小的(关于10^(-15)的)双精度数数组。如果我们按顺序计算此数组中的数字和,例如
double sum = 0;
for (int i = 0; i < n; i++) sum+=array[i];我们得到一些值x。
但是如果我们把一个数组分成几个部分,然后计算每个部分的和,然后把所有的部分和加在一起,我们就得到了一些值x2,它接近于x,但不完全是x。因此,我在计算sum时失去了累计值。
有没有人知道如何在不损失准确性的情况下,通过将这些数字分成几部分来计算这些小的双精度数的和?
发布于 2012-04-26 17:39:49
#include <numeric>
#include <iostream>
#include <vector>
struct KahanAccumulation
{
double sum;
double correction;
};
KahanAccumulation KahanSum(KahanAccumulation accumulation, double value)
{
KahanAccumulation result;
double y = value - accumulation.correction;
double t = accumulation.sum + y;
result.correction = (t - accumulation.sum) - y;
result.sum = t;
return result;
}
int main()
{
std::vector<double> numbers = {0.01, 0.001, 0.0001, 0.000001, 0.00000000001};
KahanAccumulation init = {0};
KahanAccumulation result =
std::accumulate(numbers.begin(), numbers.end(), init, KahanSum);
std::cout << "Kahan Sum: " << result.sum << std::endl;
return 0;
}输出:
Kahan Sum: 0.011101代码here。
发布于 2012-04-26 17:04:30
数字的绝对大小不是问题所在。
如果你想要一个更准确的总和,你是否考虑过补偿总和?http://en.wikipedia.org/wiki/Kahan_summation_algorithm
然而,如果你真正的意思是在不损失的任何精度的情况下,你的结果不一定适合double。如果这真的是你想要的,你可以看看http://dl.acm.org/citation.cfm?id=1824815或类似的算法908。
发布于 2012-04-26 16:51:35
在这些情况下,技巧是首先将数组从小到高排序,然后求和,然后在所做的循环中求和。这样的话,准确度是最好的。
https://stackoverflow.com/questions/10330002
复制相似问题