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!

Also Read : Explaining the Object Oriented Programming Concepts in Java

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[100] 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)

C program to calculate factorial of a large number

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[100], 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)

C program to calculate factorial of a large number

The variable that we have used to store the number of digits N digits.

#include<stdio.h> int main() {   int a[200]; //array will have the capacity to store 200 digits.   int n, i, j, carry, ndigits, x;      scanf("\%d",&n); //The logic starts      a[0]=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.

Thanks for reading

Tweet your queries and feedback to @PsychoCodes or leave a message on our Facebook page. You can also comment your questions below.

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

If you like this article, then please share it and help us grow.


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

Binary Tree in Python
02 September 2018

Image Sharpening by High Pass Filter using Python and OpenCV
17 August 2018

Explaining Register variables in C with examples
17 August 2018

C program to generate all combinations of N-Bit Binary String
10 July 2018

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

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