Finding factorial of a large number

In mathematics, the factorial of a positive integer n, denoted by n!, is the product of all positive integers less than or equal to n. For example,

5 ! = 5  \times  4  \times  3  \times  2  \times  1 = 120  \

0! is a special case that is explicitly defined to be 1.

When asked to write a program to compute factorial of a number, say n, we implement this definition into lines of code using a counter which iterates over the values from 1 to n and keep updating the result by multiplying the previous result with current value of counter. There is nothing wrong with this logic but the program fails to give correct results for 20! or higher. This is due to the limitations of the computing resources as the result becomes so large that it is not possible to store them in a 32-bit or 64-bit word.

Hence, to compute factorial of large numbers, we need to define our own logic.

Hint: Implement paper and pen method of multiplication without using Integer type variables.

Considering the limitations, we can use strings to store the numbers. The solution process breaks down as follows:

a) Since factorial involves multiplication, we need a function to multiply two numeric strings.

b)  Since multiplication involves addition, we need a function to add two numeric strings.

So, first write down a logic to add two numbers, taking care of carry over from addition of previous digits present at respectively the same position in both numbers.

Then, write a utility function to pad 0’s to a number i.e. equivalent to multiplying it by a power of 10.

Using these functions, write the logic for multiplication of two numeric strings.

I coded the solution for this in Java. The code should work for any number. I tried it for 1000! , it took around 45-60 seconds to come up with the answer and it was correct as it matched the value given in this table at wikipedia. You can have a look at it and if you find any issues with it, please let me know.

2 thoughts on “Finding factorial of a large number”

  1. nice article as wll as program.
    just want to know that when we calculate factorials of large no. , can we store those values into integrs back.
    if yes then how ?

    1. I think it is not possible to store the value back to integer as an integer is 32 bit or 64 bit, so can reach max 2^64 which is not big enough to store even 25!

Leave a Reply

Your email address will not be published. Required fields are marked *

Notify me of followup comments via e-mail. You can also subscribe without commenting.