Factorial of a Large Number in Java
We have already discussed the factorial of a number. However, we still have to discuss the factorial of a large number separately. It is because one cannot compute the factorial of a large number with the approach that is used to compute the factorial of a small number. So, in this section, we are going to discuss how to find factorial of a large number in Java. Let’s understand with the help of an example.
Example:
The factorial of number 10 is:
10! = 10 x 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1 = 3628800
The number 3628800 can be stored easily. However, the question is what if instead of 10 we have to calculate the factorial of 110? The factorial of 110 is:
The problem here is to address how to store the factorial of the number 110, which contains 179 digits?
Algorithm
Step 1: Create an array ‘result[]’ of the size maximum, where the maximum is the number of the maximum digits present in the output.
Step 2: Initialize the value stored in the array ‘result[]’ as 1 and initialize the size of the result[] array resultSize as 1.
Step 3: Do the following for all the numbers ranging from y = 2 to num.
……i) Multiply y with the result[] and update the result[] and the resultSize to keep the result of multiplication.
The algorithm mentioned above accentuates the usage of basic school mathematics. The idea is to multiply two numbers by picking one digit each of two numbers and forward the carry for the next multiplication of two digits. Let’s understand it with the help of an example.
Suppose we have to multiply 9786 with 10. Then, we will perform the multiplication like the following.
Store the number 9786 in the array as:
result[] = {6, 8, 7, 9}
y = 10
Initialize the carry as c = 0.
Do following for j = 0 to resultSize – 1
….a) Find the value of result[j] * y + v. Let the value be product.
….b) Update result[j] by storing the last digit of product in it.
….c) Update the carry by keeping the remaining digits in the carry.
j = 0, product = result[0] * y + c = 6 * 10 + 0 = 60.
result[0] = 0, c = 6
j = 1, product = result[1] * y + c = 8 * 10 + 6 = 86
result [1] = 6, c = 8
j = 2, product = result[2] * y + c = 7 * 10 + 8 = 78
result [2] = 8, c = 7
j = 3, product = result[3] * y + c = 9 * 10 + 7 = 97
result [3] = 7, c = 9
Now, put all of the digits of carry in result[] and increase resultSize by the number of digits present in carry.
Thus,
result[4] = c = 9
Hence, the result array becomes:
result[] = {0, 6, 8, 7, 9}
Now, all we have to do is to print the result array in the reverse order. Thus, 97860 is what we get when we multiply 9786 with 10.
Note: For the number 9786, we have stored its digit in the result array in the reverse order. It is because if we had have stored the digits in the same order as it is occurring in the number, then it would have become difficult to update the result[] without any extra space.
Implementation
Let’s see the implementation of the algorithm mentioned above.
Using Array
FileName: LargeNumFact.java
Output:
The factorial of the number 110 is: 15882455415227429404253703127090772871724410234473563207581748318444567162948183030959960131517678520479243672638179990208521148623422266876757623911219200000000000000000000000000
Using LinkedList
Instead of an array, one can also use a linked list to find the factorial of a large number. The good thing about using a linked list is that the linked list will not consume any extra space. It is because, unlike an array, we can allocate and deallocate the memory as per the need.
FileName: LargeNumFact1.java
Output:
The factorial of the number 110 is: 15882455415227429404253703127090772871724410234473563207581748318444567162948183030959960131517678520479243672638179990208521148623422266876757623911219200000000000000000000000000
Note: Instead of using the tail recursion in the method display(), one can also iterate over the nodes of the linked list using a loop and then display its data. However, before doing so, one has to store its nodes in a stack. It is because digits of the factorial of a number are stored in the reverse order in the linked list. Update the following code of the display() method, and one will get the same output.
Using BigInteger
One can also use the BigInteger class for computing the factorial of a large number. In this approach, we will be using the multiply() method provided by the BigInteger class. Observe the following code.
FileName: LargeNumFact2.java
Output:
The factorial of the number 110 is: 15882455415227429404253703127090772871724410234473563207581748318444567162948183030959960131517678520479243672638179990208521148623422266876757623911219200000000000000000000000000