This project is read-only.

Factorial

Nov 7, 2010 at 1:58 PM

Hi dude,

I just downloaded your library. I was looking at some of your implentation when I saw this:

        public static BigNum Factorial(BigNum num)
        {
            // HACK: Is there a more efficient implementation?
            // I know there is a way to cache and use earlier results, but not much more

            // also, note this function fails if num is non-integer. This should be the Gamma function instead

            if (num.IsZero) return 1;
            if (num < 0) throw new ArgumentException("Argument must be greater than or equal to zero", "num");
            return num * Factorial(num - 1);
        }

I didn't try but I'm sure that for 10000! the function will return a Stack Overflow exception. It's a recursive function that can call itself thousand times so it's not the best implementation.

I would suggest the following one which is still recursive but because it's tail recursive the compiler can optimize the call and generate a loop instead of thousands of call.

        public static BigNum Factorial2(BigNum num)
        {
            return Factorial2_Loop(1, num);
        }

        public static BigNum Factorial2_Loop(BigNum acc, BigNum num)
        {
            if (num.IsZero) return 1;
            if (num < 0) throw new ArgumentException("Argument must be greater than or equal to zero", "num");
            return Factorial2_Loop(num * acc, num - 1);
        }

 

You can take a look at this article explaining it: http://en.wikipedia.org/wiki/Tail_call

Cheers

EntraX