Can't get a very big sum using this array code

Question

There is a problem I'm facing where I need to take some array as input and then give their sum as output. But unfortunately I'm getting the worng output here. Can anyone explain what's wrong with this code?

#include<stdio.h>

int main()
#define N size
{
    int size,i,sum=0;;
    scanf("%d",&size);
    int a[N];
    for(i=0; i<size; i++)
    {
        scanf("%d", &a[i]);
    }
    for(i =0; i<size; i++)
    {
        sum = a[i] + sum;
    }
    printf("%d",sum);
    return 0;
}

Result:

Input (stdin)
5
1000000001 1000000002 1000000003 1000000004 1000000005
Your Output (stdout)
 705032719
Expected Output
 5000000015

You have integer overflow. Check the value of `INT_MAX` which is likely to be `2147483647`. The total won't fit `unsigned int` either, where `UINT_MAX` is probably `4294967295`. I suggest you use `long long`. — Weather Vane, Nov 30 '20 at 11:21
Definitely integer overflow. The result you're getting is equal to 5000000015 mod 2^32. To fix the problem, declare `a[N]` and `size` as `long long` variables, and replace `%d` with `%lld` in the calls to `scanf()` and `printf()`. — r3mainer, Nov 30 '20 at 11:26
Just change `int sum = 0;` to `long long sum = 0;` and change `printf("%d", sum);` to `printf("%lld", sum);` — Weather Vane, Nov 30 '20 at 11:46

score 1 · Answer 1 · answered Nov 30 '20 at 11:41

You mention your result being wrong, but when I try this on my machine I have a similar result:

Prompt>echo $(((1000000001+1000000002+1000000003+1000000004+1000000005)%2147483647))
705032721
Prompt>echo $(((1000000001+1000000002+1000000003+1000000004+1000000005)%4294967295))
705032720

What does this all mean?

Almost every basic type in C has its limitations, and integer numbers (uint or int) are limited to UINT_MAX or INT_MAX. Those values are determined by your system, but mostly they are values, like 2147483647 or 4294967295.

You seem to be using numbers, larger than those values, hence you need to use integer types with larger limitations, but be aware that those also have limitations (which are also determined by your system). In case you are interested in working with values above the limitations of your system, you might need to work with dynamical arrays of integer numbers, where the elements of your arrays are the digits, your numbers are created of.

Basile Starynkevitch · Answer 2 · 2020-11-30T12:12:33.043

You probably need some library for arbitrary-precision arithmetic, a.k.a. bignums to avoid some integer overflows. On most systems, an int has 32 bits, but see the C20 draft standard and this C reference for details. Of course, read the documentation of your C compiler (e.g. GCC).

I recommend using -for example- GMPlib. In particular because:

bignum arithmetic requires sophisticated algorithms if you want efficiency
GMPlib takes advantage of specialized hardware machine instructions and has low-level code written in assembler.

Be of course aware that GMPlib does have limitations (in particular, it is not friendly towards out-of-memory conditions). GMPlib is open source, so you can download and study its source code and even improve it.

With some recent compilers (such as GCC 10 at end of 2020) on some machines, you could use 128-bits integers (but then your program could experiment integer overflow on them, with huge numbers).

Be sure to enable all warnings and debug info, e.g. compile with gcc -Wall -Wextra -O -g

You could also consider using programming languages with bignums, such as Common Lisp (e.g. using SBCL).

Of course your computer still has a finite amount of memory, and that is a drastic limitation. See also this.

Can't get a very big sum using this array code

2 Answers2