Computing the first few (150 or so) factorials is a fairly trivial operation. The classic recursive implementation is well known and simple to understand.

fact (n):

if(n<=1)

return 1

return n * fact(n-1)

end

What happens then when we use this to try and calculate a large factorial (say >200). Depending on the system this code is running on , you will quickly run out of memory. How then can 20,000! be calculated? Some languages provide support for ‘big numbers’ or ‘bignum’. The need for such a data type is obvious. Many scientific applications require numbers that would be much larger than can be stored in the 32 bits of a standard integer. Implementations of bignum’s vary, and as such their efficiency, but the effect is the same: You can now store integers that are not bounded by their 32-bit size, but the limitations of physical memory and address space. Now with seemingly infinite space to calculate in, we are faced with the task of doing this somewhat efficiently.

The first step is to move away from the recursive definition of the function to an iterative one. In doing this we eliminate the need for a call-stack that is proportional in size to n, thus reducing the memory usage (and allowing more space to be devoted to numbers). After that, we can start putting in optimizations. There are a number of ways to go about this, and whatever way you employ would be indicative of what you were trying to do with this factorial calculation. One way to speed things up is to store various factorials in a table, and reference them instead of calculating them. Indeed, if we knew 1000!, calculating 1001! is trivial (and very fast). But, this is not so much calculation, as it uses predetermined values from a table. This is obviously a problem if you are trying to see how fast you can calculate a factorial. But if your concern is getting the value of that factorial as fast as possible, shortcuts like a lookup table would be very useful. Other things that could be done is saving the factors of 2 for the end, and then doing all those multiplications as one big bit shift. This indeed could save a lot of time, for example, in calculating 20,000!, the left shift to compensate for all powers of two would be 19,995 bits long.

The remaining tricks that really count are the reduction of the use and size of bignums. Depending on what bignum library you are using, optimizations can be done to limit the number bignums used, and try and minimize their size when they are used, as quite understandably arithmetic operations on these bignums can be quite costly.

For a more rigorous analysis (with lots of Lisp code, functional programmers rejoice!) please read the attached paper.

Comments on Factorial Programs