As a matter of factorials

Factorials can be used to calculate all kinds of useful things. A great example is, how many ways can you order a que. The simple answer is n!, or the factorial of n. So if you have a group of four persons, the number of possible ways to order them from first to last is 4! or 24.

So, how do we calculate the factorial of a number? The answer is that we calculate a factorial, by multiplying the number with all positive numbers below it. So 4! is equal to 1*2*3*4. This is the textbook example used when teaching recursion, so lets start with an example that uses recursion.

int32_t factorial(int32_t n) { if (n == 0) { return 1; } else if (n < 0) { return -1; } else { return n*factorial(n-1); } }

There are a couple of problems with the code above. The two main problems comes from the multiple function calls. One being that every call to a function will use up some stack memory. With many calls there might be problem with using too much memory. The other problem, is that each function call will take up unnecessary time. By transforming the function into a loop. No extra memory will be used, and the jumps will take up less time.

int32_t factorial(int32_t n) { int index; int32_t ret; if (n < 0) { return -1; } ret = 1; for(index = 1; index <= n; index++) { ret = ret*index; } return ret; }

Now some major improvement has been made, but there is still room for improvement. By changing the code into our next version, we can make the time constant.

int32_t factorial(int32_t n) { int32_t ret[13] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800, 479001600}; if (n < 0) { return -1; } else if (n > 12) { return -2; } return ret[n]; }

Many readers will probably assume that this doesn't solve the problem, but it does. And it does it better than the previous versions. It returns a minus one when n is less than zero, like the other. This is an error code, stating that the input is illegal. Unlike the other, this return a minus two when n is larger than twelve. This is an error code that states that the output is larger than what can be stored in a 32bit integer. You might suggest that we should switch to 64bit integers, but the problem remains, the list just goes to n equals to twenty. How to get around this problem, is something that I will go into in another article.