小双数的总和c ++

Question

假设我们10^(-15)在c ++中有一个小(大约)双数的数组.例如,如果我们按顺序计算此数组中的数字总和

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

我们得到一些价值x.

但是如果我们将一个数组分成几个部分,然后计算每个部分的总和,然后我们将所有的部分和加在一起,我们得到一些值x2,这接近x但不完全x.所以我在计算总和方面已经失去了成功.

有人知道如何通过将这些数字划分为某些部分而不会失去准确性来计算小双数的总和吗？

Answer 1

使用Kahan求和:

#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

代码在这里.