Write a c code to find the sum of squares of the first n natural numbers.

For example sum of squares of first 5 natural numbers will be 1 + 4 + 9 + 16 + 25 = 55. The mathematical formula for this would be n(n+1)(2n+1)/6.

5(5 +1)(2*5 +1)/6 = 5*6*11/6=55.

#include <stdio.h>

 int main() {

        int num, square, sum = 0, i = 1;

        printf("Enter the number n:");
        scanf("%d", &num);

        sum = num*(num +1)*(2*num +1)/6;
        /* print the sum of square of first n natural nos */
        printf("Sum of squares of first %d natural"
                        " numbers is %d\n", num, sum);

        return 0;
  }

Note: The above code is not good, as it may experience undefined behavior for large value of n, because the expression num*(num +1)*(2*n +1)/6 may suffer from integer overflow.

Let us try below example:

#include <stdio.h>

int main() {
int num, square, sum = 0, i = 1;

num=2147483647;

sum = num*(num +1)*(2*num +1)/6;
/* print the sum of square of first n natural nos */
printf("Sum of squares of first %d natural"
" numbers is %d\n", num, sum);

return 0;
}

The output:

Sum of squares of first 2147483647 natural numbers is -357913941

The above output is wrong , because 2147483647 is the maximum value that a singed integer in c can hold on 32 bit system. adding num +1 i.e 2147483647 + 1 will wrap around and becomes -2147483648. and hence result will be undefined. and also multiplying a 32 bit integer also leads to the possibility of integer overflow.

Now Let us modified above code so that we can avoid integer overflow problem>

As in the above program for storing the result and number we have used int , maximum values a `signed int’ can hold is 2147483647, and after that it will wrap around. Even if change int as unsigned long long , we may get wrong result for large number for num in our above code.

(( source from https://gmplib.org/)

Here we will use GNU MP Bignum library. GMP is a free library for arbitrary precision arithmetic, operating on signed integers, rational numbers, and floating-point numbers. There is no practical limit to the precision except the ones implied by the available memory in the machine GMP runs on. GMP has a rich set of functions, and the functions have a regular interface.

The main target applications for GMP are cryptography applications and research, Internet security applications, algebra systems, computational algebra research, etc.  here sample implementation of above code with gmp library.

/* compile this program sumsq.c */
/* gcc sumsq.c -lgmp */

#include <stdio.h>
#include <gmp.h>

int
main (void)
{

  // formula
  //sum = num*(num +1)*(2*num +1)/6;
  mpz_t num;
  mpz_t num_plus_one;
  mpz_t num_2n_plus_one;
  mpz_t num_1;
  mpz_t num_2;
  mpz_t num_6;
  mpz_t n2n;
  mpz_t resu1;
  mpz_t resu2;
  mpz_t sum;

  mpz_init_set_str (num, "2147483647", 10);    // n
  mpz_init_set_str (num_1, "1", 10);
  mpz_init_set_str (num_2, "2", 10);
  mpz_init_set_str (num_6, "6", 10);

  mpz_init (sum);
  mpz_init (num_plus_one);
  mpz_init (num_2n_plus_one);
  mpz_init (resu1);
  mpz_init (resu2);
  mpz_init (n2n);

  mpz_add (num_plus_one, num, num_1);    // n + 1

  mpz_mul (n2n, num, num_2);    // 2n

  mpz_add (num_2n_plus_one, n2n, num_1);    // 2n + 1

  mpz_mul (resu1, num, num_plus_one);    // n*(n+1)
  mpz_mul (resu2, resu1, num_2n_plus_one);    // n*(n+1)*(2n +1)

  mpz_div (sum, resu2, num_6);    // n*(n+1)*(2n +1) / 6

  gmp_printf ("%Zd\n", sum);

  /* free used memory */
  mpz_clear (num);
  mpz_clear (num_1);
  mpz_clear (num_2);
  mpz_clear (num_plus_one);
  mpz_clear (num_2n_plus_one);
  mpz_clear (num_6);
  mpz_clear (n2n);
  mpz_clear (resu1);
  mpz_clear (resu2);
  mpz_clear (sum);

  return 0;
}

Output:
3301173435788504390875217920

Note: Before compilation install GNU_Multiple_Precision_Arithmetic_Library on your platform/os. on ubuntu linux you can install libgmp-dev and libgmp3-dev package for using this library.



Related Contents to follow