The factorial of a non-negative number n, denoted by n!, is the product of all positive numbers less than or equal to n. With the usual approach, we can compute factorial only till 20! due to size limitation of data type. We have present how to overcome this limitation.

Table of content:

1. Definition of factorial
2. What if the number is large, for example 200! ?
3. Approach to find factorial of large numbers
4. Time and Space Complexity

Definition of factorial

N! = N * (N-1) * (N-2) * ... * 3 * 2 * 1

Examples:

5! = 5 * 4 * 3 * 2 * 1 = 120
7! = 7 * 6 * 5 * 4 * 3 * 2 * 1 = 5040
10! = 3628800
20! = 2432902008176640000
100! = 93326215443944152681699238856266700490715968264381621468592963895217
59999322991560894146397615651828625369792082722375825118521091686400
0000000000000000000000
200! = 7886578673647905035523632139321850622951359776871732632947425
3324435944996340334292030428401198462390417721213891963883025
7642790242637105061926624952829931113462857270763317237396988
9439224456214516642402540332918641312274282948532775242424075
7390324032125740557956866022603190417032406235170085879617892
2222789623703897374720000000000000000000000000000000000000000
000000000

As you can see 100! is so big, so you can imagine how big 1000000! will be. Such long numbers will not fit in Integer or Float datatype so we need to have our own custom data type.

What if the number is large, for example 200! ?

Types like long long int can accurately store the factorial of numbers only up to 20. So what if we have a larger number? For example, Factorial of 100 has 158 digits so it is not possible to store these many digits even if we use long long int.

To calculate factorials of larger numbers, we use the idea of old school mathematics: multiplying a number with another, one digit at a time, and taking the carry.

Steps:

To find factorial:

• We declare an array ans[] to store the result which is the factorial of the number. Let the size of this array be the maximum number of digits in the output. We need to store the output in the reverse order in this array. If we store digits in same order then we cannot update ans[] without extra space,therefore we maintain it in reverse order, i.e., digits from right to left are stored.
• We now initalise ans array to store 1 and also update the size variable to 1 storing the current size of the array.
• Now to find factorial, we take every number from 2 to n and keep on multiplying it with the number which is stored in the ans array and thereafter update the size variable.

How to multiply a number ‘x’ with the number stored in ans[]:

Approach to find factorial of large numbers

Approach

The idea here is that we multiply according to the old school mathematics I.e we one by one multiply number x with every digit of ans array.
The digits are multiplied from rightmost digit to leftmost digit, as the digits are stored in reverse order.

• initially the carry is 0.
• We need to multiply each digit of array with x therefore, for every i = 0 to size – 1 (i being the index of each digit),
  we first store the value of ans[i] * x + carry in product variable and then store the last digit of product in ans[i] and the remaining digits in carry variable.(similar to what we do in old school mathematics).
  Here we start from i=0 as the digits are placed in reverse order.
• Finally we insert the carry at the end of the ans array and update the size variable.

Let us understand this with an example:

suppose a number 6158 is stored in ans[] as-
ans[] = {8,5,1,6}
if we multiply it with x = 10
Initially carry = 0;

• i = 0,
  product = ans[0]x + carry = 810 + 0 = 80.
  ans[0] = 0, carry = 8

• i = 1,
  product = ans[1]x + carry = 510 + 8 = 58
  ans[1] = 8, carry = 5

• i = 2,
  product = ans[2]x + carry = 110 + 5 = 15
  ans[2] = 5, carry = 1

• i = 3,
  product = ans[3]x + carry = 610 + 1 = 61
  ans[3] = 1, carry = 6

• ans[4] = carry = 6

ans[] = {0,8,5,1,6}

Algorithm:
factorial(n):-

Begin
   declare ans array.
   intialise ans array as 1

   for i = 2 to n :
      multiply(i, ans)
  
End

multiply(x, ans):-

Begin
   carry = 0
   for i=0 to size-1:
      product = i*x+carry
      i = product mod 10
      carry = product / 10
   
   while carry ≠ 0:
      insert (carry mod 10) at the end of ans array
      carry = carry/10
End

Implementation in C++

#include<iostream>
using namespace std;
#define MAX  1000
  

int multiplyx(int x, int ans[], int size) 
{ 
    int carry = 0;   
    for (int i=0; i<size; i++) 
    { 
        int product = ans[i] * x + carry; 
        ans[i] = product % 10;   
        carry  = product/10;     
    } 
  
    while (carry) 
    { 
        ans[size] = carry%10; 
        carry = carry/10; 
        size++; 
    } 
    return size; 
} 
  
void factorial(int n) 
{ 
    int ans[MAX]; 
    ans[0] = 1; 
    int size = 1; 
    for (int x=2; x<=n; x++) 
        size = multiplyx(x, ans, size); 
    for (int i=size-1; i>=0; i--) 
        cout << ans[i]; 
} 
  	
int main() {
	
	int n;
	cin>>n;
	factorial(n);
	return 0;
}

Time and Space Complexity

Time Complexity: O(n log n!)

Complexity of multipy function is O(log n!). The ans array passed in represents n! . Also its length is ⌈log (n-1)!⌉(base 10). So the number of steps required will be ⌈log (n-1)!⌉(base 10)

This can be understood as to calculate n! we have (n-1!) in the ans array and the number of digits in n-1! being ⌈log (n-1)!⌉ (base 10).

For example,if (n-1)! is 1000, then the number of digits in it will be 4 and the number of steps required will be four.
And hence to calculate n! the complexity will be O(n log n!).

Space complexity: O(⌈log n!⌉)

We can clearly see that we are storing the result in ans array . So at the end ans array stores n! also the number of digits or the length of array is ⌈log n!⌉ as discussed earlier. So the space complexity is O(⌈log n!⌉).

Let us get 400! using our code and see how big is this value. :)

400! = 64034522846623895262347970319503005850702583026002959458684445942802397169186831436278478647463264676294350575035856810848298162883517435228961988646802997937341654150838162426461942352307046244325015114448670890662773914918117331955996440709549671345290477020322434911210797593280795101545372667251627877890009349763765710326350331533965349868386831339352024373788157786791506311858702618270169819740062983025308591298346162272304558339520759611505302236086810433297255194852674432232438669948422404232599805551610635942376961399231917134063858996537970147827206606320217379472010321356624613809077942304597360699567595836096158715129913822286578579549361617654480453222007825818400848436415591229454275384803558374518022675900061399560145595206127211192918105032491008000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

So by the end of this article at OpenGenus, you must have a good understanding of how to find the factorial of large numbers.