sum of positive integer returning negative number - C

Question

Beginner in C language. I suspect it may be due to overflow, but could not solve this simple exercise: program to compute the sum of squares of all the natural numbers smaller than 10000

I initially tried:

#include <stdio.h>

int main() {
   
    int a = 10000;
    
    int square(int num) {
        return num * num;
    };
    
    int total = 0;
    while (a > 0) {
        a--;
        total += square(a);
        //printf("a is %d and square is %d and total %d \n", a, square(a), total );
    
    }; 
    
    printf("total is %d ", total );
    
    
    
    return total;
}

result: total is -1724114088

and here there's the strange thing:

...
a is 9936 and square is 98724096 and total 2063522144 
a is 9935 and square is 98704225 and total -2132740927 
...

So I tried to change total to long, tried to change declaring square function as long square(int num ), but nothing changed.

Could you explain why the sum turns negative ? Is it due to overflow ? But why not resetting to 0 or positive, instead of going negative ? how can I know how many bits for int are there in a computer that I don't know (e.g. cloud ? E.g. I am coding here: [https://www.programiz.com/c-programming/online-compiler/]

Which is best practice to fix it ?

Answer 1

Do not define function in functions.

int main() {
   int square() { // NO!

Functions belong at file scope:

int square() { //OK
}
int main() { //OK
}

The code compiles because compilers have extensions to the language. It's not part of the C programming language.

Could you explain why the sum turns negative ?

See ex. why the value of sum is coming out to be negative? and other questions. The sum "wraps around" on your platform.

Is it due to overflow ?

Yes.

But why not resetting to 0 or positive, instead of going negative ?

Because systems nowadays are twos-complement, it's simpler to implement a single hardware instruction for adding numbers then two separate instructions with special overflow semantics. Unsigned and signed twos-complement numbers behave the same when doing operations on them, so instead of doing special semantics on overflow, when adding signed numbers they are added the same as they would be unsigned (bits are just added) and the result is then interpreted as a signed number (in a C program), which because the most significant bit becomes set the number becomes negative.

Anyway, compiler just does not care, because signed overflow is undefined behavior compiler does not have to care. The compiler just generates a hardware instruction for signed addition, which behaves as explained above.

how can I know how many bits for int are there in a computer that I don't know

You can check your compiler documentation.

But usually it's simpler to just compile a simple C program where you use CHAR_BIT - the number of bits in a byte - and sizeof(int) - the number of bytes in an int - and inspect the output of that program. For example, a program such as:

#include <stdio.h>
#include <limits.h>
int main() {
    printf("There are %d bits in int\n", (int)sizeof(int) * CHAR_BIT);
}

Note that number of bits in types does not only change with platform and operating systems, it can change with compiler, compiler versions and also compilation options.

Which is best practice to fix it ?

This depends on what behavior do you want.

To calculate bigger values use a bigger datatype - long or long long. When the language features are not enough, move your program to use some big number library.

If you want to terminate the program in case of problems - you can check for overflow and call abort() or similar if it happens.

Answer 2

You'll need to change all uses of int to long:

#include <stdio.h>

int main() {
   
    long a = 10000;
    
    long square(long num) {
        return num * num;
    };
    
    long total = 0;
    while (a > 0) {
        a--;
        total += square(a);
        //printf("a is %ld and square is %ld and total %ld \n", a, square(a), total );
    
    }; 
    
    printf("total is %ld ", total );
    
    return 0;
}

which prints total is 333283335000

EDIT

Or you could just change the total, the return type of square, and perform the appropriate casts when computing the squared values:

#include <stdio.h>

int main() {
   
    int a = 10000;
    
    long square(int num) {
        return (long)num * (long)num;
    };
    
    long total = 0;

    while (a > 0) {
        a--;
        total += square(a);
        //printf("a is %ld and square is %ld and total %ld \n", a, square(a), total );
    
    }; 
    
    printf("total is %ld ", total );
    
    return 0;
}

Produces the same result shown above.

onlinegdb here

Answer 3

Instead, you could have used a formula.

Sum of Squares of first N natural numbers = (N * (N + 1) * (2 * N + 1) / 6

For now, let N be 10000.

Ignoring the 6 in the formula, the sum of squares is as big as 10^12. It will not fit in an integer. You should use a data type that can accommodate bigger values, like long or long long int.

Here's the modified code.

#include <stdio.h>

int main() {
   
    int a = 10000;
    
    int square(int num) {
        return num * num;
    };
    
    // Change int to long long int
    long long int total = 0;
    while (a > 0) {
        a--;
        total += square(a);
        //printf("a is %d and square is %d and total %d \n", a, square(a), total );
    
    }; 
    
    
    // Change %d to %lld
    printf("total is %lld ", total );
    
    
    
    return total;
}