I will tell you what this is about. I saw a simple looking problem on HackerEarth about finding factorial of given numbers. It looks easy, but another look at the constraints (1<=N<=100) changes everything. Well, not everything, especially if you are going to write it in languages like Python (“dynamically typed”) which has built-in capabilities to handle big numbers, but it is really a trouble to do it in C or any such statically typed language.
So first of all, what exactly is the difference between statically and dynamically typed languages. Dynamically typed languages require their interpreters to detect the type of the variable from the value that is assigned to it. On the other hand, in statically typed languages, the type of the variables must be known at compile time.
Some believe the latter has advantages over the former. As we explicitly state the type, run time errors are reduced and run time performance increases. We won’t get into that discussion here.
So our problem
Before getting into it, I will first write the Python code that worked flawlessly and gave answers to factorials of over 100.
As you can see, it doesn’t get any easier for anybody, no matter how novice he is with programming. But how does one solve the same problem with languages with no native support for big (of order >10^100) numbers? Simple. We make use of algorithms. The first thing that pops in one’s mind when dealing with numbers this large is the use of arrays. Yes, that is the right way to go, or at least the one that worked for me.
So here is the plan. We create an array of integers which will hold a digit in each index, starting with the least significant bit. For example, if we were to store the number 12345 in the array, we would do it like this:
| 5 | 4 | 3 | 2 | 1 |
|---|
That is, array[0] stores ‘5’, array[1] stores ‘4’ and so on. We have reversed the number for a specific reason. For knowing that reason, you have to go back to your 2nd grade class where you were taught to multiply two two-digit numbers. How did you do that?
| 4 | |||
|---|---|---|---|
| 2 | |||
| 3 | 7 | ||
| x | 6 | 3 | |
| 1 | 1 | 1 | |
| 2 | 2 | 2 | 0 |
| 2 | 3 | 3 | 1 |
Got the memory back? Although it may seem a trivial thing now, notice that you never do a multiplication whose result is more than 81, that is, 9×9 which is the product of largest two single digit numbers. So can you somehow make the computer follow the same method to calculate the factorial, such that it never does a >81 digit addition in the entire process, which is well inside the size of the shortest numeric data type in C (unsigned short: 65,535)? Yes, of course. We are coders, right? 😉
To start off, we will need variables. We will use num to accept the input number whose factorial is to be found out. cur stores the result of the calculation i * arr[j] + temp. The least significant digit from cur (for example 3, in case of 123) goes into arr[j] while the remaining digits get stored in the temp variable. Follow the above step till the end of the array which we initially denote by pos variable. pos is initialized and assigned 1, as we initialize our arr[] with arr[0]=1 (since we will be using this value to multiply subsequent 2,3,4…num, we don’t want our answer to evaluate to 0).
After this loop, we will need to empty out the carry forward integer in our temp variable. It will be done in the reverse order as well, but here, we will increment pos to make it always point to the number of digits in arr[].
Finally you can print our the arr[] in the reverse order to get the expected answer and this should not surprise you since we have been doing storing of the numbers in reverse order in our arr[]. Here is the C++ code that I wrote. I didn’t cross check the results for larger values of num, so take care with that.
So that was it for this short article. I am reading more on GMP (GNU Multiple Precision Arithmetic Library) that is written exactly for this purpose. Nevertheless, it is always good to know how to do it by hand. Thank you.