C++ series summation code giving different answers on large input

Question

I am adding numbers from 1 to n in C++. I have used both the iteration method and mathematical formula. The code works fine for up to 9 digits.

But when I give input a 10 digit number, the formula and iteration methods give separate answers.

I have tried to look it up on google but couldn't find any solution for this. My code:

#include <bits/stdc++.h>
using namespace std;

int main(){

    unsigned long long i, n, sum = 0, out_put;
    cout << "Sum of numbers from 1 to: ";
    cin >> n;

    /// using mathematical formula
    out_put = n*(n+1);
    out_put = out_put/2;
    cout << " =   " << out_put << endl;

    /// using iteration
    for (i=1; i<=n; i++){
        sum = sum+i;
    }
    cout << " ==  " << sum << endl;

    return 0;
}

How do know which one is the correct one? If I assume the formula can't be wrong then why is the iteration method giving incorrect answer? I have used unsigned long long to prevent overflow but still didn't work.

Answer 1

What you are seeing is overflow happening on your calculations at different points. 9,999,999,999 * 10,000,000,000 is ~9.9e19 while an unsigned long long holds ~1.8e19. So the result wraps around and you get one answer.

Your for loop is also going to overflow but it is going to do so at a different point meaning the answers will diverge from one another since the modulo arithmetic is happening with a smaller number.

Answer 2

Your problem is that n*(n+1) can be too large to store in an unsigned long long, even though the end result (half of that) which you calculate via iteration may still fit.

Assuming your unsigned long long has 64 bits, it can hold integers up to 18446744073709551615. Anything above that will restart from 0.

Edit: As Nathan points out, you can of course have both calculations overflow. The sum would still give the correct result modulo 2^64, but the direct calculation can be off because the division does not generally yield the same result modulo 2^64 after you have wrapped around.