Sum of first n natural numbers

Question

Trying to learn C I'm toying around a bit with some for loops and sums. I want to compute the sum of the first n natural numbers without using the mathematical formula n(n+1)/2. I have this code for it:

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

int main() {
    int n = 100;
    int sum = 0;

    for (int ix = 0; ix <= n; ix++) {
        sum = sum + ix;
    }

    printf("Sum of the first %d natural numbers is %d\n", n, sum);
}

So for n = 100 I get the sum to be 5050, which is correct. I also get correct when I use n = 10000, however if I go for example n = 1000000 then I get the sum = 1784293664 but correct answer should be sum = 500000500000.

Why does my program stop working when n becomes larger and what is that number of the sum being displayed when n = 1000000?

Does this answer your question? [C integer overflow](https://stackoverflow.com/questions/12335784/c-integer-overflow) — Mad Physicist, Sep 09 '20 at 17:16
you can double the max value if you use unsigned int, but it will still overflow for what you are trying to do. The best you can do is unsigned long long int, unless you get creative and use a additional variable to store the most significant digits once they are about to be too big for the data type (just know they are really divided by some factor of 10). For example. 2878 could be num1 being 2 and num2 being 878. https://en.wikipedia.org/wiki/C_data_types — Kurt E. Clothier, Sep 09 '20 at 17:37
@KurtE.Clothier "you can double the max value if you use unsigned int," more like `*1.414` than double. Still, using a wider type like `unsigned long long` or `uintmax_t` certainly affords more range. — chux - Reinstate Monica, Sep 09 '20 at 17:52
@chux-ReinstateMonica - I'm using emacs and I only work from the terminal. — Parseval, Sep 09 '20 at 18:08
@chux-ReinstateMonica I was meaning the max output before overflow, but yes, only about 1.414x of the max input n before that overflow. Good maths. — Kurt E. Clothier, Sep 10 '20 at 19:38

Vlad from Moscow · Accepted Answer · 2020-09-10T09:41:36.307

If you want to calculate a sum of natural numbers then instead of the type int use the type unsigned int.

Correspondingly declare the variable sum as having the type unsigned long long int to decrease the risk of overflow.

For example

unsigned int n = 100;
unsigned long long int sum = 0;

for ( unsigned int ix = 1; ix <= n; ix++){
   sum = sum + ix;
}

printf("Sum of the first %u natural numbers is %llu\n" , n, sum);

Or you could include the header <inttypes.h> and use the type uintmax_t for the variable sum as it is shown in the demonstrative program below.

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

int main(void) 
{
    unsigned int n = 1000000;
    uintmax_t sum = 0;

    for ( unsigned int ix = 1; ix <= n; ix++){
       sum = sum + ix;
    }

    printf("Sum of the first %u natural numbers is %" PRIuMAX "\n" , n, sum);
    
    return 0;
}

The program output is

Sum of the first 1000000 natural numbers is 500000500000

Pay attention to that there is no need to introduce the auxiliary variable ix. The loop can look simpler as for example

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

int main(void) 
{
    unsigned int n = 1000000;
    uintmax_t sum = 0;

    while ( n ) sum += n--;
    
    printf( "Sum of the first %u natural numbers is %" PRIuMAX "\n" , n, sum );
    
    return 0;
}

Thank you this made it work. However, I don't understand how a type can be long long and int? Could you elaborate on this? — Parseval, Sep 09 '20 at 17:41
@Parseval There are the following integer types for example for signed types int or signed or signed int, long or long int, long long or long long int. — Vlad from Moscow, Sep 09 '20 at 17:48
@Parseval: `short`, `long`, `signed` and `unsigned` are type specifiers that can be combined with `int` or without another type specifier with the same semantics: `long long x;`, `long long int x;`, `long int long x;` and `int long long x;` are equivalent definitions. — chqrlie, Sep 09 '20 at 18:43

score 1 · Answer 2 · edited Sep 09 '20 at 18:44

1

int type is too small to contain numbers so huge, so an arithmetic overflow happens on the way up there. What you observe is called undefined behaviour (UB for short), this is what officially happens in C when signed integers overflow (unsigned ones simply rollover to zero and on).

edited Sep 09 '20 at 18:44

chqrlie

131,814
10
121
189

answered Sep 09 '20 at 17:18

bipll

11,747
1
18
32

Hi, thanks for your answer. But does this mean that in C, one is not able to work with large numbers or is there a way around this? I want to clock this operation, that is, I want to know how long it takes to calculate the first n natural numbers. – Parseval Sep 09 '20 at 17:20
Unless you want to implement it yourself, you use a library specifically for handling large numbers, such as https://gmplib.org/ – Shane Reilly Sep 09 '20 at 17:24
There's such thing as https://en.m.wikipedia.org/wiki/List_of_arbitrary-precision_arithmetic_software, see Libraries with C in Language column. – bipll Sep 09 '20 at 17:36

score 1 · Answer 3 · answered Sep 09 '20 at 17:20

1

You are hitting variable type 'int' limit. Try using long data type to store the sum.

answered Sep 09 '20 at 17:20

Mausom Saikia

150
1
9

Thanks for your answer. Unfortunately long data type did not solve the issue. – Parseval Sep 09 '20 at 17:22

score 1 · Answer 4 · answered Oct 13 '21 at 03:15

1

#include<stdio.h> int main(){

int i=0, sum=0, n=10;

while(i<=n){
    printf("%d\n",i);
   sum=sum+i;
i++;
}
printf("%d",sum);

return 0; }

answered Oct 13 '21 at 03:15

Gaurav Shinde

11
3

Sum of first n natural numbers

4 Answers4