Thursday, July 22, 2010

Factorial Function in C#

 The Factorial Function is a classic interview question. It opens the doors to a discussion about stack overflow (if done recursively) and integer overflow (if the param is too large) as well as discussions around how to handle and catch errors.

Here is one way to do it using recursion:

static Int64 Factorial(int factor)
{
    if (factor > 1)
    {
        return factor * Factorial(--factor);
    }
    return 1;
}

Here is another way to do it using a loop: 

static Int64 Factorial(int factor)
{
    Int64 factorial = 1;
    for (int i = 1; i <= factor; i++)
    {
        factorial *= i;
    }
    return factorial;
}

Neither function does any sanity checks for input (e.g. >= 1) and assumes that we're looking for a factorial of 1 or greater.

There's a third and much better way to do factorials if you are going to use them in code that needs to be optimized. In fact I can't think of a reason why you wouldn't want to use the following method. If you are calculating an Int64 factorial then the maximum factor that you can calculate it for is 20. After that it will overflow the Int64 type. If you are calculating an Int32 factorial then the highest you can go is 12. 

static Int64[] factors64 = { 0, 1, 2, 6, 24, 120, 720, 5040, 40320,
362880, 3628800, 39916800, 479001600, 6227020800, 87178291200,
1307674368000, 20922789888000, 355687428096000, 6402373705728000,
121645100408832000, 2432902008176640000 };
 
static Int64 Factorial(int factor)
{
    return factors64[factor];
}

The tests that I ran showed the recursive factorial function to run 14 times slower than the array lookup and the loop to run 5 times slower.

8 comments:

  1. Amen Brother. I have been asked this question so many times on job interviews. And for a double (floating point being so slow), the double max is 170 factorial. Thats an array of 170 doubles. If you just index it your like very ZEN with code optimization. That could really matter if the calculation is at the center of a very repetitive call to the factorial function.

    ReplyDelete
  2. As far as I remember 0!=1

    ReplyDelete
  3. august: What part of the code sample assumes that zero is equal to one?

    ReplyDelete
  4. It seems like factors64[0]=0. I think it should be factors64[0]=1

    ReplyDelete
  5. One more thing. In my previous code 0!=1 should read zero factorial is equal to one. This is not the same as 0 not equal to 1. ! is sign of factorial in math

    ReplyDelete
  6. august: You are correct, that is a bug in the code. I'm going to leave it as is right now and not edit it (I may edit it later) as it seems to be a good twist to the question. From my experience, however, most candidates are not aware of the mathematical factorial equation and so that would slip them by. It slipped by me because I wasn't paying attention.
    Also, I understand your notation I just wasn't expecting to see mathematical notation and so read that as if it was C#. My bad and thanks again for pointing that out.

    ReplyDelete
  7. Ahhh, so obvious once it's pointed out. Very nice solution.
    Trevor.

    ReplyDelete
  8. Fast and also not hard coded.
    static decimal[] mfactors = null;
    static double[] dfactors = null;
    static void init_mFactors()
    {
    mfactors = new decimal[27];
    mfactors[0] = 1;
    decimal f = 1;
    for (int i = 1; i < 27; i++)
    {
    f *= i;
    mfactors[i] = f;
    }
    }
    static void init_dFactors()
    {
    dfactors = new double[171];
    dfactors[0] = 1;
    double f = 1;
    for (int i = 1; i < 171; i++)
    {
    f *= i;
    dfactors[i] = f;
    }
    }
    public static decimal Factorial(int factor)
    {
    if (mfactors == null) init_mFactors();
    if (factor < 0 || factor > 26) throw new OverflowException("Arithmetic operation resulted in an overflow.");
    return mfactors[factor];
    }
    public static double Factorial(double factor)
    {
    if (mfactors == null) init_dFactors();
    if (factor < 0 || factor > 170) throw new OverflowException("Arithmetic operation resulted in an overflow.");
    return dfactors[(int)factor];
    }
    }

    ReplyDelete