Wrong result when calculating the sum of 1 to n using loop

Question

I want to calculate sum of 1 to n using loop and this is my C code:

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char *argv[]){
    long sum = 0;
    int n = atoi(argv[1]);
    for(int i = 1; i<= n; i++)
        sum += i;
    printf("Sum of serial from 1 to %d = %ld\n", n, sum);
    return 0;
}

when I run the program with small n, the result is correct but when I run with large number this is wrong. Here is the result when I run this:

./sum 100000
Sum of serial from 1 to 100000 = 705082704

Answer 1

It looks like long in your environment is 32-bit long and the maximum value it can hold is 2,147,483,647. The sum of integers from 1 to 100,000 is 5,000,050,000, which exceeds the limit.

In C99 and later, you can use long long type, whose maximum value is at least 9,223,372,036,854,775,807.

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char *argv[]){
    long long sum = 0;
    int n = atoi(argv[1]);
    for(int i = 1; i<= n; i++)
        sum += i;
    printf("Sum of serial from 1 to %d = %lld\n", n, sum); // use %lld to print "long long" value
    return 0;
}

int64_t type in inttypes.h may be supported by more compilers.

#include <stdio.h>
#include <stdlib.h>
#include <inttypes.h>

int main(int argc, char *argv[]){
    int64_t sum = 0;
    int n = atoi(argv[1]);
    for(int i = 1; i<= n; i++)
        sum += i;
    printf("Sum of serial from 1 to %d = %" PRId64 "\n", n, sum); // use PRId64 macro to print "int64_t" value
    return 0;
}

Answer 2

Use unsigned large types to avoid undefined behaviour (UB) and easily detect the problem.

#include <stdint.h>

unsigned long long sum(unsigned long num)
{
    unsigned long long result = 0, previous = 0;

    for(unsigned long i = 1; i <= num; i++)
    {
        result += i;
        if(result < previous)
        {
            printf("Wraparound at : %lu\n", i);
            break;
        }
        previous = result;
    }
    return result;
}

int main(void)
{
    printf("%llu\n", sum(1000000));
    printf("%llu\n", sum(6074001001UL));
}

https://ideone.com/g6isU6

Answer 3

The C standard only guarantees at least 16 bits of width for int and 32 bits for long

The sum of numbers from 1 to n, where n is a k bit number, needs 2*k bits at most and 2*k-1 bits at least

100000 is already out of range for that minimum size of int, needing 17 bits. A safe choice for it would be using long (but in general you should sanitize your input to fit in the chosen type)

Its sum needs at least 33 bits. A safe choice for it would be using long long (C99)

Or you could use the types in the stdint header for better control (C99)

Also, please notice:

• atoi causes UB when the value is not representable;
• for (int i=1; i<=n; i++) causes UB when n==INT_MAX (*)
• sum += i causes UB when sum + i is not representable

(*): using unsigned instead causes an infinite loop which if it has no side effects is UB

Answer 4

the data type of the variable "sum" is "long", which has a maximum value of 2^31-1, or approximately 2.1 billion. you can fix this issue by using data type that can store larger values, such as "long long" or "unsigned long long".

Answer 5

I'm guessing you're running it on a 32-bit machine, or using a 32-bit compiler. You need to force 64-bit arithmetic, because you overflowed a 32-bit signed container with a number that was 33 bits unsigned.

1. #include <inttypes.h> at the top, to get access to fixed-size types and printf() macros.
2. Change the types of sum, i and n to uint64_t: 64-bit unsigned int.
3. Instead of atoi(), use strtoull() (allows users to specify numbers in bases other than decimal, and gives a guaranteed unsigned long long) - or, better still, sscanf(argv[1], SCNu64, &n), which you know will guarantee to parse a uint64_t.
4. Change your printf() line to printf("Sum of serial from 1 to " PRIu64 " = " PRIu64 "\n", n, sum); so that you see the full 64-bit values.

It should all work after that. (Arguably, you could get away with uint32_t for n, but you may as well use 64-bit throughout.)

Incidentally, you should check that argc is at least 2 before looking at argv[1], otherwise the outcome will be (1) undefined and (2) definitely undesirable. Checking argv[1] consists entirely of valid numerals would be a good idea too, or that sscanf() returns 1, which indicates it successfully parsed the one item requested.

Answer 6

Overflow

Code experienced signed integer overflow, which is undefined behavior (UB).

Instead code could detect the upcoming problem.

for(int i = 1; i<= n; i++) {
  if (i > LONG_MAX - sum) {
    fprintf(stderr, "Sum is out of range\n");
    break;
  }
  sum += i;
}

Code can use wider types to forestall the problem, yet the problem can remain for larger n.
Note: even INT_MAX == LLONG_MAX is possible.

Answer 7

That sum is n*(n+1)/2, which results in 100000*(100000 + 1) / 2 = 5000050000. That is far over the maximum long 32 bit integer (only in case your long is 32 bit, which seems to be the case, see below) operating in two's complement, you should have gotten that amount minus 4294967296 (2^32) or 705082704 (which is the value you are showing printed out)

Use

#include <stdint.h>

and declare your sum variable as uint64_t, that grows up to 18446744073709551615 (the maximum value of that type) and avoids the overflow until you reach the value 6074001001 (by adding, don't make the calculation with the formula I use above that you will get an overflow before dividing by 2 and will get a wrong result again) that will overflow (but it overflows before the 32 bit int you use for the loop index i, which overflows at 2147483648)