Calculating factorial of large numbers in C

Admin 1
Viewed 48464

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);
}
c algorithm
16 Answers

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
user_24103590

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

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.

user_151680
Related