sum of small double numbers c++

c++, double, numbers, sum

Solution

Using 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;
}

Output:

Kahan Sum: 0.011101

Code here.

Problem

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]; ``` we get some value `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?

Original source

Related problems