Any better way to implement factorials?

Question

I have been working on a library to handle numbers exceeding the normal bounds of 8 bytes for long long (usually).

I'm talking hundreds to thousands of digits.

Now I have implemented a function for factorials looking like this:

largeNum factorial(largeNum& input) {
    if (input > one) return (input * factorial(input-one));
    else return one;
}

Now this gives me good results. 100! took about 5 seconds to calculate and that's already above 150 digits. The result was correct.

Though 5 seconds is a long time 200 would already take minutes to calculate.

WolframAlpha, for example, can calculate 100000! in less than 10 seconds.

So there's gotta be a better way to do it. I've been looking on https://en.wikipedia.org/wiki/Factorial for the so-called Gamma function and was wondering if that would help in any way.

Answer 1

Although it is hard to optimize code without seeing the implementation, you can certainly pick up some cycles by converting your recursive function to an iterative one, or by helping compiler do it for you by optimizing tail call.

largeNum factorial(largeNum& input) {
    largeNum res = one;    
    while (input > one) {
        res *= input;
        input -= one;
    }
    return res;
}

Of course, this is just a different implementation of the same "middle school" approach to computing factorials. If you are looking for an advanced algorithms, here is a page dedicated to comparing various "hard" implementations.