# C program to find factorial of Large Numbers

Some experiences in computing factorials iteratively with the following code:

``#include <stdio.h> long long int factorial(int n) {   long long ans = 1;   int i;   for(i=1; i <= n; i++)   ans *= i; return ans; } void main() {   int x;   for(x=10; x <= 21; x++)//to calculate factorial upto 21       printf("\%lld", factorial(x)); }``

Output for the following code will be:

`39916800`

`479001600`

`6227020800`

`87178291200`

`1307674368000`

`20922789888000`

`355687428096000`

`6402373705728000`

`121645100408832000`

`2432902008176640000`

`-4249290049419214848`

So, we can now see that even when using the long long data type, the maximum factorial we can get correctly, is only 20!

It is impossible to calculate factorials of a number greater than 20 by using the defined data type available.

Alternatively, let’s recall the manual way we used to multiply

` 17`

` x 18`

` ---------`

` 136`

` +17`

` __________`

` 306`

` __________`

The numbers involved in the intermediate calculations never exceed 81 as 9*9 = 81 which is the highest possible single digit product possible

Data Structure to be formed here is,

Say int a is array where we can store 100 1-digit numbers (each position can store an integer, but we will only store 1 digit for each position) While calculating we use the array to store each digit at one location of the array. The number of digits that is stored in the array(The result) we call N digits, above ndigits=3.

Now, only one digit is stored at every position of an array a, When we get a carry we need to add it at each position. Let’s call the variable to hold the carry, carry.

We have so far developed and understood how to design structure, let’s get Coding.
We face One Simple Problem, though,

How do we store a number in the array, and why do we store it the way we do?

The numbers are actually stored «backwards» for convenience, for Example:

1279 would be saved in an array a, as:

a = [9,7,2,1];

This is done such that when the digit by digit calculations are being performed, the «carry» can be placed on the positions of the array with a higher index. This way, we are sure that carry is computed and placed correctly on the array.

` 17`

` x 8`

` (5) (stored in carry)`

` + 86 (stored in x )`

`----------`

` 136 (after adding carry in array)` The variable that we have used to store the number of digits N digits.

``#include<stdio.h> int main() {   int a; //array will have the capacity to store 200 digits.   int n, i, j, carry, ndigits, x;      scanf("\%d",&n); //The logic starts      a=1;  //initializes array with only 1 digit, the digit 1.      ndigits=1;    // initializes digit counter      carry = 0; //Initializes carry variable to 0.      for(i=1; i<=n; i++)  // variable i will go upto n-the Number of which factorial need to be found      {           for(j=0; j<ndigits; j++) //variable j will iterate upto the number of digits ndigits            {              x = a[j]*i+carry; //x contains the digit by digit product               a[j]=x\%10; //Contains the digit to store in position j              carry = x/10; //Contains the carry value that will be stored on later indexes           }            while(carry>0) //while loop that will store the carry value on array.            {               a[ndigits] = carry\%10;              carry= carry/10;              ndigits++; // increments digit counter            }     }             for(i=ndigits-1;i>=0;i--) //printing answer             printf("\%d",a[i]);             printf("");   return 0; }``

The Above Program is the answer to our solution.

Also, don’t forget to subscribe to our Newsletter.

Preorder and Postorder Traversal of binary tree in Python
02 September 2018

Binary Tree in Python
02 September 2018

Explaining Register variables in C with examples
17 August 2018

Data Autosave System using PHP, MySQL and AJAX
06 July 2018

Понравилась статья? Поделиться с друзьями: