CODEWITHSUNDEEP
calgorithm
ronk
ronk

Reputation:

Calculating factorial of large numbers in C

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. Is there any way to handle factorial of large numbers in C?

The compiler I'm 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);
}

Upvotes: 20

Views: 50818

Answers (16)

Michael F
Michael F

Reputation: 40889

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

Upvotes: 1

cletus
cletus

Reputation: 625465

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 10157, which takes at least 525 bits to store accurately as an integer.

Upvotes: 40

Jonathan Leffler
Jonathan Leffler

Reputation: 755094

Factorials up to 12! fit into a 32-bit integer. Factorials up to 20! fit into a 64-bit integer. After that, you've run out of bits on most machines. However, 34! fits into an unsigned 128-bit integer, 57! fits into a 256-bit integer, and 98! fits into an unsigned 512-bit integer. To calculate 100! as an integer, you need at least 525 bits.

This bc script calculates factorials (up to 35! but you can change the limit easily):

#!/usr/bin/bc -l

define f(n) {
   auto r, i
   r = 1
   for (i = 1; i <= n; i++)
   {
       r *= i;
       print "n = ", i, ", log2 = ", l(r)/l(2), ", n! = ", r, "\n"
   }
}

f(35)
quit

And some sample values:

# Key values
# n =  1, log2 =   0.00000000000000000000, n! = 1
# n =  2, log2 =   1.00000000000000000000, n! = 2
# n =  3, log2 =   2.58496250072115618147, n! = 6
# n =  4, log2 =   4.58496250072115618149, n! = 24
# n =  5, log2 =   6.90689059560851852938, n! = 120
# n =  6, log2 =   9.49185309632967471087, n! = 720
# n =  7, log2 =  12.29920801838727881834, n! = 5040
# n =  8, log2 =  15.29920801838727881836, n! = 40320
# n =  9, log2 =  18.46913301982959118130, n! = 362880
# n = 10, log2 =  21.79106111471695352921, n! = 3628800
# n = 11, log2 =  25.25049273335425078544, n! = 39916800
# n = 12, log2 =  28.83545523407540696694, n! = 479001600
# n = 13, log2 =  32.53589495221649912738, n! = 6227020800
# n = 14, log2 =  36.34324987427410323486, n! = 87178291200
# n = 15, log2 =  40.25014046988262176421, n! = 1307674368000
# n = 16, log2 =  44.25014046988262176426, n! = 20922789888000
# n = 17, log2 =  48.33760331113296117256, n! = 355687428096000
# n = 18, log2 =  52.50752831257527353551, n! = 6402373705728000
# n = 19, log2 =  56.75545582601885902935, n! = 121645100408832000
# n = 20, log2 =  61.07738392090622137726, n! = 2432902008176640000
# n = 21, log2 =  65.46970134368498166621, n! = 51090942171709440000
# ...
# n = 34, log2 = 127.79512061296909618950, n! = 295232799039604140847618609643520000000
# n = 35, log2 = 132.92440362991406264487, n! = 10333147966386144929666651337523200000000
# ...
# n = 57, log2 = 254.48541573017643505939
# n = 58, log2 = 260.34339672530400718017
# ...
# n = 98, log2 = 511.49178048020535201128
# n = 99, log2 = 518.12113710028496163045
# n = 100, log2 = 524.76499329005968632625

For the factorials 57!, 58!, 98!, 99!, 100! I've omitted the factorial value as it spreads over multiple lines in the output and isn't all that important. Note that 100! requires at least 525 bits of precision.

This code is available in my SOQ (Stack Overflow Questions) repository on GitHub as file factorial.bc in the src/miscellany sub-directory.

You could use double or long double to extend the range of values, but you lose some accuracy.

Upvotes: 1

Kokul Jose
Kokul Jose

Reputation: 1752

Here is a solution for your question:

#include <stdio.h>
void factorial(int b){
    int temp = 0, r, size = 0, x;
    int arr[200] = {0};
    int l_b = b-1;
    while(b>0){
        r = b%10;
        arr[size++] = r;
        b = b/10;
    }
    while(l_b >= 2){
        int i=0;
        while(size>0){
         x = arr[i]*l_b+temp ;
         arr[i++] = x%10;
         temp = x/10;
         size--;
        }
       while(temp>0){
          arr[i++] = temp%10;
          temp = temp/10;
       }
      size = i;  --l_b;
    }
    for(int k=size-1;k>=0;k--)
        printf("%d",arr[k]);//ok i'm taking space here
    printf("\n");
}
int main(void) {
    // your code goes here
    int fact;

    scanf("%d\n",&fact);
    factorial(fact); 

    return 0;
}

Upvotes: 1

chux
chux

Reputation: 154592

Any ways to handle factorial of large numbers in C ?

As factorials can rapidly exceed the range of standard fixed width integers and even floating point types like double, Code should consider a user type that allows for unbounded integer precision for an exact answer.

Various wide integer precision libraries exist, yet if code needs a simple solution, consider using a string.

The below is not fast, nor mindful of arrays bounds, yet is illustrative of the idea. The converting of '0'-'9' to/from 0-9 so much is wasteful, yet this does allow easy step-by-step debugging.

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

static char *strfact_mult(char *s, unsigned x) {
  unsigned sum = 0;
  size_t len = strlen(s);
  size_t i = len;
  while (i > 0) {
    sum += (s[--i] - '0') * x;
    s[i] = sum % 10 + '0';
    sum /= 10;
  }
  while (sum) {
    len++;
    memmove(&s[1], s, len);
    s[i] = sum % 10 + '0';
    sum /= 10;
  }
  return s;
}

char *str_fact(char *dest, unsigned n) {
  strcpy(dest, "1");
  while (n > 1) {
    strfact_mult(dest, n--);
  }
  return dest;
}

void test_fact(unsigned n) { 
  char s[1000];
  printf("%3u %s\n", n, str_fact(s, n));
}

int main(void) {
  test_fact(0);
  test_fact(4);
  test_fact(54);
  test_fact(100);
}

Output

  0 1
  4 24
 54 230843697339241380472092742683027581083278564571807941132288000000000000
100 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

Upvotes: 1

sud03r
sud03r

Reputation: 19799

To approximately 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)

Upvotes: 15

solsTiCe
solsTiCe

Reputation:

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

Upvotes: 2

Garen
Garen

Reputation: 961

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.

Upvotes: 0

jhuni
jhuni

Reputation: 425

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.

Upvotes: -4

Jitse Niesen
Jitse Niesen

Reputation: 4542

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).

Upvotes: 1

Steve Weet
Steve Weet

Reputation: 28422

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);

Upvotes: 5

Christoph
Christoph

Reputation: 169833

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);
}

Upvotes: 9

varzan
varzan

Reputation: 587

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)

Upvotes: 18

rmn
rmn

Reputation: 2391

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.

Upvotes: 1

gshauger
gshauger

Reputation: 745

100! = 933262154439441526816992388562667004907159682643816214685929 6389521759999322991560894146397156518286253697920827223758251185210 916864000000000000000000000000

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

Upvotes: 0

Stefano Borini
Stefano Borini

Reputation: 143935

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.

Upvotes: 0

Related Questions