Finding the factorial of a large number

Before delving into the computation of factorial for large numbers, it's essential to understand the concept itself. Let's have a look into what is factorial actually.

Factorial of a number??

Factorial is applicable only to non-negative integers and represents the product of all integers equal to or smaller than a given value, denoted by the symbol '!'. For example, factorial of a number 'n' is given by,

$$n!=n*(n-1)(n-2)......21$$

Simple Program to find the Factorial of a number

Various programming approaches, such as recursion and iteration, can be employed to calculate the factorial of a number. Let's examine one of these methods:

#include <iostream> 
using namespace std; 
unsigned int factorial(unsigned int n) 
{ 
    if (n==0 || n==1) 
        return 1; 
    return n*factorial(n-1); 
} 
int main() 
{ 
    int num;
    cin>>num;
    cout<<num<<"! = "<<factorial(num)<<endl;
    return 0; 
}

Time Complexity: O(n)
Auxiliary Space: O(n)

After reviewing the code above, it may seem that obtaining the factorial of a number is pretty straightforward. While it is indeed easy for small numbers, but there comes a challenge when dealing with larger numbers, such as 100.

To illustrate this point, consider running the aforementioned code for 5!. It works flawlessly, producing the correct result of 120. However, attempting the same for 50 does not yield accurate output. This observation highlights the complexity that arises when dealing with larger numerical values.

Program to find the Factorial for a Large number

When examining the factorial of 100, it becomes apparent that the result comprises 158 digits. Storing such a large outcome poses a challenge, even when utilizing a data type like "long long int." The fundamental approach we adopt in this scenario involves employing basic mathematical multiplication.

#include <iostream>
using namespace std;
#define MAX 500
int multiply(int x,int result[],int size);
void factorial(int n)
{
    int result[MAX],size=1;
    result[0]=1;
    for(int i=2;i<=n;i++)
        size=multiply(i,result,size);
    for(int i=size-1;i>=0;i--)
        cout<<result[i];
}
int multiply(int x, int result[], int size)
{
    int carry=0;
    for(int i=0;i<size;i++){
        int product=result[i]*x+carry;
        result[i]=product%10;
        carry=product/10;
    }
    while(carry){
        result[size]=carry%10;
        carry=carry/10;
        size++;
    }
    return size;
}
int main()
{
    int num;
    cin>>num;
    factorial(num);
    return 0; 
}

Time Complexity: O(n*log(n!))
Auxiliary Space: O(max(digits in factorial))

To gain a clearer explanation of the above provided code, follow the steps outlined below.

1. Begin by creating an array called result[] with a maximum size to accommodate the factorial result, ensuring the number of digits matches the maximum size.

2. Set the initial size of the array result[] to 1, representing the size of the array, and initialize the value stored in result[] as 1.

3. Multiply x with result[] and update both result[] and size to store the multiplication results for all numbers ranging from x = 2 to n.

4. To achieve this, sequentially multiply x with each digit of result[] one by one.

5. Certainly! To execute the multiply function, follow these steps:

   1. Set carry to 0.

   2. Iterate through i from 0 to size-1.

   3. Calculate the product by finding the value of result[i] * x + carry.

   4. Update result[i] by storing the last digit of the product in it.

   5. Update carry by storing the remaining digits in it.

6. Place each digit of the carry into the result[] array and increment the size by the number of digits in the carry.

   Thanks for reading. Hope you find it useful. Happy Learning!!🐥
   Connect me at X, LinkedIn🤝