Calculating factorial of large numbers in C

Question

Hello,

In my C code , i want to calculate the factorial for numbers in the range 1 to 100. For small numbers, the function works but for bigger numbers for example 100! it returns incorrect result. Any ways to handle factorial of large numbers in C ?. The compiler im using is gcc v4.3.3 . My code is as follows :

#include <stdio.h>
#include <math.h>

double print_solution(int);

int main(void)
{
        int no_of_inputs,n ;

        int ctr = 1;

        scanf("%d",&no_of_inputs); //Read no of inputs

        do
        {
                scanf("%d",&n); //Read the input

                printf("%.0f\n",print_solution(n));

                ctr++;  

        }while(ctr <= no_of_inputs);


        return 0;       
}

double print_solution(int n)
{
        if(n == 0 || n == 1)
                return 1;
        else
                return n*print_solution(n-1);


}

Answer 1

I guess that's because you are overflowing the int range, which is up to approx. 2 billions. You can get up to 4 billions if you use unsigned int, but beyond that you have to use the bigint library.

Answer 2

No standard C data type will accurately handle numbers as large as 100!. Your only option if to use arbitrary precision integer arithmetic, either through a library or done by yourself.

If this is just some hobby project, I'd suggest trying it yourself. It's kind of a fun exercise. If this is work-related, use a pre-existing library.

The largest C data type you'll normally get is a 64 bit integer. 100! is in the order of 10¹⁵⁷, which takes the better part of 500 bits to store accurately as an integer.

Answer 3

100! = 933262154439441526816992388562667004907159682643816214685929 6389521759999322991560894146397156518286253697920827223758251185210 916864000000000000000000000000

You can't represent a number this big with an int or a long.

Answer 4

100 factorial is huge, to be precise it's 93326215443944152681699238856266700490715968264381621468592963895217 59999322991560894146397615651828625369792082722375825118521091686400 00000000000000000000.

Maybe you should use a bignum library like GMP. It's got nice docs, a pretty consistent interface, speed and if you're on Linux your distro probably has a package (I think mine installs it by default)

Answer 5

This is most certainly due to overflow. You need a way to represent large numbers (unsigned long long won't even cover up to 25!).

Answer 6

you could try going for "unsigned long long" type, but thats the maximum you can get with built in types. I'd suggest (as cletus has already mentioned) either going with a known implementation of big numbers, or writing one yourself. "its a nice exercise" x 2.

Answer 7

If you don't want to use a bigint library, the best you can do with the stdlib is using long double and tgammal() from math.h:

long double fact(unsigned n)
{
    return tgammal(n + 1);
}

This'll get you 100! with a precision of 18 decimals on x86 (ie 80 bit long double).

An exact implementation isn't that complicated either:

#include <math.h>
#include <stdio.h>
#include <string.h>

void multd(char * s, size_t len, unsigned n)
{
    unsigned values[len];
    memset(values, 0, sizeof(unsigned) * len);
    for(size_t i = len; i--; )
    {
        unsigned x = values[i] + (s[i] - '0') * n;
        s[i] = '0' + x % 10;
        if(i) values[i - 1] += x / 10;
    }
}

void factd(char * s, size_t len, unsigned n)
{
    memset(s, '0', len - 1);
    s[len - 1] = '1';
    for(; n > 1; --n) multd(s, len, n);
}

int main(void)
{
    unsigned n = 100;
    size_t len = ceill(log10l(tgammal(n + 1)));
    char dstr[len + 1];
    dstr[len] = 0;
    factd(dstr, len, n);
    puts(dstr);
}

Answer 8

Everyone is telling you the correct answer however a couple of further points.

1. Your initial idea to use a double to get a wider range is not working because a double can not store this data precisely. It can do the calculations but with a lot of rounding. This is why bigint libraries exist.

2. I know this is probably an example from a tutorial or examples site but doing unbounded recursion will bite you at some point. You have a recursive solution for what is essentially an iterative process. You will understand why this site is named as it is when you try running your program with larger values (Try 10000).

A simple iterative approach is as follows

  int answer, idx;

  for (answer = 1, idx = 1; idx <= no_of_inputs; idx++ ) {
    answer = answer * idx;
  }
  printf("Factorial of %3d =  %d\n", no_of_inputs, answer);

Answer 9

If you want to use only the standard data types and you do not need the exact answer, then compute the logarithm of n! instead of n! itself. The logarithm of n! fits easily in a double (unless n is huge).

Answer 10

Don't use the recursive algorithm I think, it is super slow, even if it is cached it will be slow. This is just something you should consider.

The reason for this is when you call fact(100) you don't actually run it 100 times, you actually run that function 5050 times. Which is bad, if it is cached then it could be 100 times, however, it is still slower to run a function call with if statements then to run a loop.

double print_solution(int n)
{
    double rval = 1;
    unsigned int i;

    for( i = 1; i <= n; i++ ) {
     rval *= i;
    }

    return rval;

}

Using arbitary-precision arithmetic you could make it go very high, however, you need to use a library to do that, or you could make your own library, but that would take a lot of time to do.

Answer 11

To compute factorials of large numbers you can go this way:

n! =  n * (n-1)!
so log(n!) = log(n) + log(n-1!)

Now you can use dynamic programming to compute log(n!) and calculate
n! as (base)^(log-value)

Answer 12

Yet another (free) lib you could look into is libtommath:

http://math.libtomcrypt.com

Answer 13

In addition to the advice of others, I'd suggest getting familiar with the storage limits of the basic types (int, long, long long, ...) for whatever computer/platform you're actually using. ("When in doubt, print more out!")

One earlier poster referred to an 80-bit precision limit, but that's particular to an x86 CPU.

Another person cited ISO C90 several times, although C99 is the latest standard; even if many compilers haven't completely implemented C99, you will probably find that they very-very likely at least have support for long long, which should correspond to >= 64-bit precision.

Answer 14

this is what i made to solve a google riddle some years ago, it uses GMP library http://gmplib.org/:

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

void fact(mpz_t r,int n){
    unsigned int i;
    mpz_t temp;
    mpz_init(temp);
    mpz_set_ui(r,1);
    for(i=1;i<=n;i++){
        mpz_set_ui(temp,i);
        mpz_mul(r,r,temp);
    }
    mpz_clear(temp);
}
int main(void) {
    mpz_t r;
    mpz_init(r);
    fact(r,188315);
    /* fact(r,100); */
    gmp_printf("%Zd\n",r);
    mpz_clear(r);
    return(0);
}

gcc -lgmp -o fact fact.c

./fact

Answer 15

Why C when you got a program in assembly that can handle upto 255! !!!! See code : Assembly code to calculate upto 255!

Answer 16

You Can Not store a number greater than 19 digits in int. The longest data type available in C is long long, this can only store integers up to 10^19. let me give U a trick. Generally, U are told to calculate the factorial of large nos in programming contests. In such contests, your time starts at the time when u enter the no to calculate its factorial, it would be better if u calculate the factorials and store them somewhere,and print them as required, and if u start calculating the factorial then u will surely exceed time limit provided by them. IF u are thinking till where U will store the factorials then let me tell u, they also provide U a source limit, U need to calculate factorials till there.

Factorial of 18 will cross the range of long ling. So, U should use some other method like storing in Arrays. You can use character array or int array to solve your problem. Choose the one that U can implement without ant error. I used integer Array and calculated factorial of 1000.While using array U are required to store a number at an array index. This program is at my blog under Programming Section. In that program I have used an structure to store different details of the factorial like length of array, and value of factorial. Check Out this program at my blog.

My Blog's address is comphacks.wordpress.com.