std::partial_sum and Kahan algorithm

Question

In C++11 I want to calculate the partial sum of a vector using std::partial_sum.

std::vector<double> vec = {-1.0, 0.1, 0.1, 0.1, 0.1, 0.1, 0.1, 0.1, 0.1, 0.1, 0.1}; std::partial_sum(vec.begin(), vec.end(), vec.begin());

Unfortunatelly, the last entry of the resulting vector is 1.38778E-16 due to rounding errors of doubles and the fact that 0.1 has no exact presentaion as double.

vec = {-1.0, 0.9, 0.8, 0.7, 0.6, 0.5, 0.4, 0.3, 0.2, 0.1, 1.38778E-16};

Is there any chance to use the Kahan algorithm in std::partial_sum to reduce rounding errors and get a smaller error - something like

std::partial_sum(vec.begin(), vec.end(), vec.begin(), KahanSum);

Are you OK with passing a function with side effects as the operation (namely updating the running compensation term)? — user555045
– user555045, Commented Feb 20, 2015 at 18:13

Community · Accepted Answer · 2020-06-20 09:12:55Z

You can implement Kahan summation on top of std::partial_sum (based on Wikipedia pseudocode):

double c = 0.0; std::partial_sum(vec.begin(), vec.end(), vec.begin(), [c](double sum, double elem) mutable -> double { double y = elem - c; double t = sum + y; c = (t - sum) - y; return t; });

This still won't get you zero though, since (double)0.1 is exactly equal to 0.1000000000000000055511151231257827021181583404541015625 and so the exact sum of your array is about 5.5511151231E-17 (assuming standard double).

Great, excatly what I wanted. Didn't know about mutable. Thank you!
For VS2010 I had to add a "-> double" after the mutable keyword.
Added that in. It is necessary in C++11 - as opposed to C++14. I'm quite surprised that neither clang nor gcc warn about this.

Collectives™ on Stack Overflow

std::partial_sum and Kahan algorithm

1 Answer 1

3 Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Related