小双数的总和c ++

2022-01-09 00:00:00 numbers sum double c++

假设我们在 c++.如果我们按顺序计算这个数组中数字的总和，例如

Assume that we have an array of small (about 10^(-15) ) double numbers in c++. If we calculate the sum of numbers in this array sequentially, for example 

double sum = 0;
for (int i = 0; i < n; i++) sum+=array[i];

我们得到一些值x.

但是，如果我们将一个数组分成若干部分，然后计算每个部分的总和，然后将所有部分总和相加，我们会得到一个值 x2，它接近于 x 但不完全是 x.所以我在计算总和时失去了准确性.

But if we divide an array into some parts and then calculate the sum in each part and after this we add all the partial sums together we get some value x2, which is close to x but not exactly x. So I have lost accruacy in calculating sum.

有人知道如何在不损失准确性的情况下通过将这些数字分成一些部分来计算小双数的总和吗?

Does someone know how to calculate the sum of small double numbers by partitioning these numbers into some parts without loosing accuracy?

推荐答案

使用Kahan Summation:

#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

代码这里.

相关文章