Why is the integer summation in C language incorrect?

Question

#include <stdio.h>
int main(void)
{
    unsigned sum = 0;
    for (unsigned i = 1; i <= 100000; i++)
    {
        sum += i;
    }
    printf("%lld", sum);
    return 0;
}

Output:705082704

But the correct answer should be 5000050000

Answer 1

The unsigned integer type on your machine is almost certainly 32-bits. The largest number this type can hold is 4294967295. Your expected result is larger than this, so integer overflow occurs.

The solution is to use a larger data type for sum.

If you include <stdint.h> you might wish to use uint64_t, giving it a max potential value of 18446744073709551615.

As noted by ikegami, you'll also want to provide the correct format specifier when printing a uint64_t value. Typically rather than %lld you'd use %llu. To ensure you get the correct specifier (and there are many) you can include <inttypes.h> and use the PRIuN family of macros. They're listed on the page linked earlier.

E.g.

printf("%" PRIu64 "\n", sum);

If this looks odd to a C beginner, the PRIu64 preprocessor macro inserts the string literal "llu", and neighboring string literals are treated as one continuous string literal by the compiler.

Answer 2

The reason for this behavior is unsigned integer overflow. In C, unsigned integer overflow is required to wrap around (but that's not the case for signed integers, though).

Everything seems to point towards the fact that the size of the unsigned type on your machine is 4 bytes, which can store values up to 2^32 - 1 = 4294967295 before it wraps around. You can check the size of a type with sizeof(<the_type>) (i.e., sizeof(unsigned) in your case).

In your case, the largest value of i just before sum overflows is 92681, amounting to an accumulated sum of 92682 * 92681 / 2 = 4294930221 ¹, which is less than 4294967295. Then you add 98682 and get 4294930221 + 98682 = 4295022903, which cannot fit in an unsigned int on your machine, so it wraps around to 4295022903 % 2^32 = 55607.

Move the print statement into the for-loop to see this in action. You should see something like

.
.
.
4294559503
4294652181
4294744860
4294837540
4294930221
55607
148290
240974
333659
426345
519032
611720
.
.
.

Lastly, note that the result you're getting is equal to 500050000 % 2^32.

ps. You might want to look up format specifiers for printing.

---

¹https://en.wikipedia.org/wiki/1_%2B_2_%2B_3_%2B_4_%2B_%E2%8B%AF

Answer 3

As you said "But the correct answer should be 5000050000", but max value of unsigned int is 4294967295, 5000050000 > 4294967295, so unsigned int can not hold the result, you need to use bigger type, such as unsigned long long, max value of this type is 18446744073709551615, which is larger than 5000050000, it can let you get correct result.

When you run the following code:

#include <stdio.h>
#include <limits.h>
int main(void)
{
    unsigned int sum = 0;
    printf("unsigned int max value is %u\n", UINT_MAX);

    unsigned long long  LongSum = 0;
    printf("unsigned long long value is %llu\n", ULLONG_MAX);
    for (unsigned i = 1; i <= 100000; i++)
    {
        LongSum += i;
    }
    printf("%llu\n", LongSum);
    return 0;
}

You will seer the following output, demonstrating the impact of using the two different int types.

unsigned int max value is 4294967295
unsigned long long value is 18446744073709551615
5000050000