std::accumulate not acting as expected

Question

I am getting an unexpected result using std::accumulate with test code. I am trying to add up a large vector of doubles but for some reason the value is overflowing:

#include <iostream>
#include <vector>
#include <functional>
#include <numeric>

using namespace std;

double sum(double x, double y)
{
    // slows things down but shows the problem:
    //cout << x << " + " << y << endl;
    return (x+y);
}

double mean(const vector<double> & vec)
{
    double result = 0.0;

    // works:
    //vector<double>::const_iterator it;
    //for (it = vec.begin(); it != vec.end(); ++it){
    //      result += (*it);
    //}

    // broken:
    result = accumulate(vec.begin(), vec.end(), 0, sum);

    result /= vec.size();

    return result;
}


int main(int argc, char ** argv)
{

    const unsigned int num_pts = 100000;

    vector<double> vec(num_pts, 0.0);

    for (unsigned int i = 0; i < num_pts; ++i){
        vec[i] = (double)i;
    }

    cout << "mean = " << mean(vec) << endl;

    return 0;
}

Partial output from the cout inside the sum:

2.14739e+09 + 65535
2.14745e+09 + 65536
-2.14748e+09 + 65537
-2.14742e+09 + 65538
-2.14735e+09 + 65539

Correct output (iterating):

mean = 49999.5

Incorrect output (using accumulate):

mean = 7049.5

I am probably making a tired mistake? I have used accumulate successfully before...

Thanks

It happened to overflow exactly on n = 65536 because SUM(0..n) = (n)(n+1)/2. Isn't math great — Wug, Jun 05 '13 at 22:05
You might want to use [Kahan Summation](https://en.wikipedia.org/wiki/Kahan_summation_algorithm). See my answer to [sum of small double numbers c++](http://stackoverflow.com/questions/10330002/sum-of-small-double-numbers-c). — Peter Wood, Jun 05 '13 at 22:07
possible duplicate of [C++ std::accumulate doesn't give the expected sum](http://stackoverflow.com/questions/3604478/c-stdaccumulate-doesnt-give-the-expected-sum) — jogojapan, Jun 06 '13 at 03:33

score 9 · Accepted Answer · answered Jun 05 '13 at 21:35

9

You need to pass a double to accumulate:

result = accumulate(vec.begin(), vec.end(), 0.0, sum);
                                            ^^^

otherwise the accumulation is performed using int, and then converting the result to a double.

answered Jun 05 '13 at 21:35

juanchopanza

223,364
34
402
480

One minute and thirty seconds. It amazes me how fast you guys notice things like this. +1 – Wug Jun 05 '13 at 21:36
@Wug we might have made the same mistake before :) – juanchopanza Jun 05 '13 at 21:37
10

@Wug: This is a standard gotcha with `std::accumulate`. Half the people probably guessed the answer before the page was even loaded, just from the title. – Kerrek SB Jun 05 '13 at 21:37

std::accumulate not acting as expected

1 Answers1

Linked

Related