Simple factorial solutions

A few days ago I posted a simple recursive factorial example to my Facebook page. I asked for non-recursive alternatives and I received quite a few responses. Here are some of my thoughts.

The problem with a recursive solution is that it uses a lot of stack memory. Every function call pushes data onto the stack, and this is expensive. While an iterative solution may still have a complexity of O(n), it will still tend to be faster because it’s not pushing the stack on every iteration.

For example, my original factorial example:

long rFactorial( long n )
{
    if(n <= 1) return 1;
    else return n * rFactorial(n - 1);
}

For every iteration this function will make another function call, and when it returns its value, it must return the value from each iteration of the function.

On the other hand, here’s an iterative version:

long iFactorial( long n )
{
    long r = 1;
    if(n > 1) r *= n--;
    return r;
}

For every iteration this function simply multiplies, assigns a value, and decrements an integer. No stack operations at all. My simple experiments on a Core 2 Duo Macbook Air show this to be about twice as fast as the recursive version.

The other problem here is precision. For any sizable value of n, n! is a huge number that cannot be represented by a long integer. For example, 100! would require 158 decimal digits to represent, which would take 525 bits to represent as a binary integer.

This is what bigint libraries are for. The Gnu project has an excellent bigint library called GMP (The Gnu Multiprecision Library).

Here’s how we would code this problem using GMP:

void gmpFactorial( mpz_t result, long n )
{
    long i;
    mpz_t temp;
    mpz_init(temp);
    mpz_set_ui(result, 1);
    for( i = 1; i <= n; i++ ) {
        mpz_set_ui(temp, i);
        mpz_mul(result, result, temp);
    }
    mpz_clear(temp);
}

It’s called like this:

int main( int argc, char ** argv )
{
    long n = 0;
    mpz_t result;

    if(argv[1]) {
        sscanf(argv[1], "%ld", &n);
    }

    mpz_init(result);
    gmpFactorial(result, n);
    gmp_printf("%ld! is %Zd\n", n, result);
    mpz_clear(result);
}

So there are really two problems at work here. One is the algorithm: the iterative solution clearly works better than the recursive version.

The other problem is precision: Factorials can get big really fast. Here the solution is to use a bigint library.