Cannot calculate factorials bigger than 20! ! How to do so?

Question

I am using unsigned long long integer format in order to calculate big factorials. However my code fails at some point can you have a look at it? Actually it is part of a larger code for Taylor expansion of exponential function, but that part is irrelevant at this point. I will appreciate any suggestions.

Thanks

#include <stdio.h>
#include <math.h>
//We need to write a factorial function beforehand, since we
//have factorial in the denominators.
//Remembering that factorials are defined for integers; it is
//possible to define factorials of non-integer numbers using
//Gamma Function but we will omit that.
//We first declare the factorial function as follows:
unsigned long long factorial (int);
//Long long integer format only allows numbers in the order of 10^18 so 
//we shall use the sign bit in order to increase our range.
//Now we define it,
unsigned long long
factorial(int n)
{
//Here s is the free parameter which is increased by one in each step and
//pro is the initial product and by setting pro to be 0 we also cover the
//case of zero factorial.
    int s = 1;
    unsigned long long pro = 1;
    if (n < 0)
        printf("Factorial is not defined for a negative number \n");
    else {
    while (n >= s) { 
    printf("%d \n", s);
    pro *= s;
    s++;
    printf("%llu \n", pro);
    }
    return pro;
    }
}

int main ()
{
    int x[12] = { 1, 5, 10, 15, 20, 100, -1, -5, -10, -20, -50, -100};
//Here an array named "calc" is defined to store 
//the values of x.
unsigned long long  k = factorial(25);
printf("%llu \n", k);

//int k;
////The upper index controls the accuracy of the Taylor Series, so
////it is suitable to make it an adjustable parameter. 
//int p = 500;
//for ( k = 0; k < p; k++);

}

Answer 1

The limit on an unsigned long long is 18446744073709551615, or about 1.8e+19. 20! is about 2.4e+18, so within range, however 21! is about 5.1e+19, exceeding the maximum size of an unsigned long long.

You may find this helpful: Are there types bigger than long long int in C++?

Answer 2

You're overflowing your integer type. It's likely that unsigned long long is 64 bits long for you.

• 20! is 0x21c3_677c_82b4_0000 which fits.
• 21! is 0x2_c507_7d36_b8c4_0000 which does not fit.

You can look into libraries like GMP which enable arbitrarily large integers.

---

To extend the GMP comment. Here's some code that will calculate the factorial using GMP:

void factorial(unsigned long long n, mpz_t result) {
    mpz_set_ui(result, 1);

    while (n > 1) {
        mpz_mul_ui(result, result, n);
        n = n-1;
    }
}

int main() {
    mpz_t fact;
    mpz_init(fact);

    factorial(100, fact);

    char *as_str = mpz_get_str(NULL, 16, fact);
    printf("%s\n", as_str);

    mpz_clear(fact);
    free(as_str);
}

This will calculate factorial(100), and results in:

0x1b30964ec395dc24069528d54bbda40d16e966ef9a70eb21b5b2943a321cdf10391745570cca9420c6ecb3b72ed2ee8b02ea2735c61a000000000000000000000000

---

And just for fun, here's the C++ version. Constructors, destructors and operator overloading tend to make the C++ version of these things look a bit cleaner. The result is the same as before.

#include <gmpxx.h>
#include <iostream>

int main() {
    mpz_class fact = 1;

    for (int i=2; i<=100; ++i)
        fact *= i;

    std::cout << "0x" << fact.get_str(16) << "\n";
}

Answer 3

Range of unsigned long long is usually 0 to 2^64 - 1 (18,446,744,073,709,551,615). 21! goes out of this range.

Answer 4

Indeed:

2^64 = 18446744073709551616
21!  = 51090942171709440000
20!  =  2432902008176640000

By the way, to calculate the result of a series (e.g., Taylor) you should not calculate each term separately; this will definitely bring you problems such as this one. Instead, try to calculate each term by reusing the previous one.

For example, the Taylor series for cos requires the summation of terms like:

(-1)^i * (x^(2*i)) / (2i)!

It is easy to see that each term can be calculated easily from the previous one:

newterm = - oldterm * x^2 / ((2i+1)*(2i+2))

So, I believe that you don't need to calculate large factorials, for what you're trying to do. On the other hand, if you need to, you'll have to use a library for big numbers, such as gmp.