9

The output is 705032704 instead of 5000000000. Why is that? I thought std::accumulate would compute the sum of the elements in the vector. 

#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <string>
#include <iterator>
#include <queue>
#include <stack>
#include <numeric>

typedef long long ll;

int main()
{

    std::vector<ll> nums = {1000000000, 1000000000,1000000000,1000000000,1000000000};
    std::cout << std::accumulate(nums.begin(), nums.end(), 0);
    std::cin.ignore();

}
JFMR
  • 23,265
  • 4
  • 52
  • 76
Ruirui
  • 149
  • 7

3 Answers3

8

Integer overflow.

std::accumulate infers the type of summing variable from the type of third argument. Since you pass in an integer, the result of std::accumulate will also be an integer.

Pass long long literal instead (from C++11):

std::accumulate(nums.begin(), nums.end(), 0LL);
Yksisarvinen
  • 18,008
  • 2
  • 24
  • 52
6

The standard algorithm std::accumulate is declared the following way

template<class InputIterator, class T>
T accumulate(InputIterator first, InputIterator last, T init);

So the template parameter T is used as the type of the accumulator.

In this call

std::accumulate(nums.begin(), nums.end(), 0)

the deduced type of the parameter T is int because the integer literal 0 has the type int. As a result there is an overflow of the sum stored in the accumulator of the type int.

You have to use at least the long long integer literal 0ll as

std::accumulate(nums.begin(), nums.end(), 0ll)

or maybe it is reasonable to use a double floating literal

std::accumulate(nums.begin(), nums.end(), 0.0 )

Here is a demonstrative program

#include <iostream>
#include <vector>
#include <iterator>
#include <numeric>

using ll = long long int;

int main()
{
    std::vector<ll> nums = {1000000000, 1000000000,1000000000,1000000000,1000000000};
    std::cout << std::accumulate( std::begin( nums ), std::end( nums ), 0ll ) << '\n';
    std::cout << std::accumulate( std::begin( nums ), std::end( nums ), 0.0 ) << '\n';
}

Its output is

5000000000
5e+09
Vlad from Moscow
  • 301,070
  • 26
  • 186
  • 335
  • Why isn't OP's code throwing an overflow exception? `int` is signed. – Spencer Aug 06 '19 at 12:04
  • 1
    @Spencer Neither the algorithm nor the operation throws an exception. – Vlad from Moscow Aug 06 '19 at 12:07
  • 2
    @Spencer -- overflow of a signed integer type produces undefined behavior. That could involve throwing an exception, but that's not required and not at all common. – Pete Becker Aug 06 '19 at 12:41
  • @PeteBecker That's good to know. To me, this means the standard explanation for avoiding unsigned integer types (silent wrapping) doesn't hold water. – Spencer Aug 06 '19 at 13:35
  • @Spencer -- despite the undefinedness, the behavior of signed overflow is typically benign. It's whatever the processor does, which typically means wrapping to the smallest value of the type. But that's not guaranteed, of course. – Pete Becker Aug 06 '19 at 15:05
  • @PeteBecker Yes, as proved by OP's experience. I was compelled to comment because the (to me) bad advice against unsigned integers is a pet peeve. – Spencer Aug 06 '19 at 15:59
  • Can you use the `0ull` literal instead of `0ll`? They are all non-negative. – JFMR Aug 07 '19 at 05:58
  • @ElProfesor It can be used provided that all elements of the vector are non-negative. – Vlad from Moscow Aug 07 '19 at 09:42
4

You don't sum into a long long but in a int, try this

#include <vector>
#include <algorithm>
#include <iostream>
#include <numeric>

int main()
{

    std::vector<ll> nums = {1000000000, 1000000000,1000000000,1000000000,1000000000};
    std::cout << std::accumulate(nums.begin(), nums.end(), 0ll);
    std::cin.ignore();

}
NathanOliver
  • 171,901
  • 28
  • 288
  • 402
Martin Morterol
  • 2,560
  • 1
  • 10
  • 15