C Handle factorial with big numbers

Question

I'm trying to calculate 52! using C language. But it seems that somehow, I can't handle big numbers. I can't telle if it's my compiler or if I'm doing it wrong..

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

uint64_t factorielle(int n) {
   if(n == 0)
       return 1;
    else
      return n * factorielle(n-1);
}

int main(int argn, char** argv) {

  printf("Number : %"PRId64"\n", factorielle(52));

  return 0;
}

I get this result :

Number : -8452693550620999680

I tryed with GCC 5.3.0, GCC 7.2.0 and Zapcc 5.0.0

Thanks a lot !

Answer 1

You can never represent 52! in any of the C integer types (64 bit). One solution is to use your own data structure to represent that big a value or try to find some library (such as GMP which provides that facility.

You can check that the value of 2^64 itself is 1.8446744e+19 which is far smaller than 8.0658175e+67. So there's no way possible using integer types in C.

Some more thoughts into You can never represent 52! in any of the C integer types

^{As it is being mentioned, it is not possible for many of the system which use 64 bit integer types (int64_t). Let's delve into the matter. (54! requires 238 binary units). With a type of int256_t, it is would be possible to represent 52!. But int256_t is not a standard type as of now. The DEC VAX even supported operations on 128-bit integer. As mentioned by chux even now various compilers support 128 bit integer types and operations, so it is not an impossible feat to extend it to support the 256 bit integer types. Then I guess it couldn't be said You can never represent 52! in any of the C integer types}

Answer 2

Read more about factorials.

^{Hint: it is always useful to read a little bit before coding if you are not familiar with the subject.}

Try to find out an estimate of the factorial of 52 (e.g. of its logarithm). For that purpose, you might use Stirling's approximation. You'll discover that it is really a big number (much bigger than 2⁶⁴-1, which is generally the largest number your C implementation can handle).

Consider using some arbitrary precision arithmetic (a.k.a. "bignum"s) library such as GMPlib. BTW, efficient bignum libraries are really difficult to code (so you'll do much worse than what existing libraries give you) because their algorithmics is very difficult.

Perhaps you don't need to compute such a big factorial.

Answer 3

Factorial of 54 is

230843697339241380472092742683027581083278564571807941132288000000000000

which is too big to handle by any primitive data types in C.

If you are trying to implement a factorial program to calculate factorials of such big numbers then you can follow this tutorial.