BlogsDope image BlogsDope

How to calculate 100 factorial (100!) in C

June 7, 2017 FACTORIAL LOOP C FUNCTION 10961

Calculating 100 factorial (100!) may sound ordinary at the first glance because writing a code for factorial calculation is not at all a tough job but storing such a large number definitely requires some extra effort. The factorial of 100 (100!) is 93326215443944152681699238856266700490715-
9682643816214685929638952175999932299156089-
4146397615651828625369792082722375825118521-
0916864000000000000000000000000
 which is 158 digits long and the maximum value of unsigned long long int in C is 18,446,744,073,709,551,615. So, how you are gonna store such a large number?

The solution is simple. We will make an array and store each digit of the number as elements of the array. For example, we will store 4256 as

6 5 2 4

Yes, we have stored the number with its digits reversed. The logic of doing so will be clear soon.

Now the real problem comes to calculate the factorial and store its digits in this form and this doesn’t require any high-level mathematics. We just need to follow what we have learned when we were kids i.e., multiplication of two numbers by multiplying digit by digit.

1234
*  4
----
4936

Here, we multiplied 4*4 first and wrote 6 (from 16) and the carry left was 1 and then we multiplied 3*4 and added carry to it i.e., 12+1 = 13. So, we wrote 3 and the carry left over was 1. We then multiplied 4 with 2 and added the carry 1 to get 9 and finally 4 with 1.

Did you notice that we were getting a single digit number in each step with some carry and we will fill our array with these single digit numbers to get the final result. So after first step of multiplying 4*4, we will fill our array with 6.
4*4 = 16 Number to write – 6 Carry – 1

6 0 0 0

In the next step, we will multiply 4*3 and add the carry left in the previous step.
(4*3)+1 = 13 Number to write – 3 Carray – 1

6 3 0 0

(4*2)+1 = 9 Number to write – 9 Carray – 0
Again, we will multiply 2 with 4 and add the carry of previous step.

6 3 9 0

(4*1)+0 = 4 Number to write – 4 Carray – 0
And finally, 4*1.

6 3 9 4

As we have dealt with the logic of filling the array, let’s come to the real problem of calculating the factorial of the number.

Before dealing with the real calculation of factorial, let’s write the code of multiplication of two numbers and storing the result in an array.

We will first make an array to store the digits of the result of multiplication and store the first number in the array.

#include <stdio.h>
#define MAX_DIGIT 200

int main()
{
    int fact[MAX_DIGIT] = {1,2,3,4};
    return 0;
}

We have made an array ‘fact’ and made all its elements 0.

Now, we will make a variable to keep the record of the number of digits currently in the result.

#include <stdio.h>
#define MAX_DIGIT 200

int main()
{
    int fact[MAX_DIGIT] = {4,3,2,1};
    int number_of_digit = 4,i,carry = 0;
    return 0;
}

Now, we will do the multiplication (we are multiplying 1234 with 10 in this example).
 

#include <stdio.h>
#define MAX_DIGIT 200

int main()
{
    int fact[MAX_DIGIT] = {4,3,2,1};
    int number_of_digit = 4,i,carry = 0;

    for(i=0; i<number_of_digit; i++)
    {
        int x = fact[i]*10; //product
        fact[i] = (x+carry)%10;
        carry = (x+carry)/10;
        //we are at end of the number with some carry remaining
        //number of digit will increase by 1
        if (i == number_of_digit-1 && carry>0)
            number_of_digit++;
    }

    //to display the calculated factorial
    for(i=number_of_digit-1; i>=0; i--)
    {
        printf("%d",fact[i]);
    }
    printf("\n");

    return 0;
}
1234
* 10
____
   0 carry - 4

1234
* 10
____
  40 carry - 3

1234
* 10
____
 340 carry - 2

1234
* 10
____
2340 carry - 1

1234
* 10
____
12340

Let’s understand the for loop step by step.

int x = fact[i]*10 – fact[i] is 4. So, x is 40.

fact[i] = (x+carry)%10 – ‘carry’ is 0. So, fact[i] will become 0. We updated fact[i] as we were doing in the multiplication by hand.

carry = (x+carry)/10 – The carry will become 4.

Similarly in the next step, int x = fact[i]*10 will evaluate to x = 3*10 and fact[i] = (x+carry)%10 will make fact[i] (30+4)%10 i.e., 4. Finally, ‘carry’ will become 3. Similarly, we will continue further.

After understanding the code of multiplication, the factorial calculation is very simple. We will just iterate from 1 to the number and do the multiplication. So for calculating the factorial of 4, we will first multiply 1 with 2 and store the result in the array and then multiply the result in the array with 3 and then again store this result in the array and finally, we will multiply this result with 4 and store this result in the array.

So, after multiplication of 1 by 2.

2

After multiplication of this result by 3.

6

Again, multiplying the result by 4.

4 2
#include <stdio.h>
#define MAX_DIGIT 200

int main()
{
    int fact[MAX_DIGIT] = {4,3,2,1};
    int number_of_digit = 4,i,carry = 0;

    for(i=0; i<number_of_digit; i++)
    {
        int x = fact[i]*10; //product
        fact[i] = (x+carry)%10;
        carry = (x+carry)/10;
        //we are at end of the number with some carry remaining
        //number of digit will increase by 1
        if (i == number_of_digit-1 && carry>0)
            number_of_digit++;
    }

    //to display the calculated factorial
    for(i=number_of_digit-1; i>=0; i--)
    {
        printf("%d",fact[i]);
    }
    printf("\n");

    return 0;
}

 


Liked the post?
Developer and founder of CodesDope.
Editor's Picks
1 COMMENT

Please login to view or add comment(s).