Originally Posted by
Salem
Factorial grows so quickly that it's feasible to cache all the answers in an array as you calculate them.
Indeed. 22! is too big to be stored in a 64 bit unsigned type. Only 21 results to be computed, and that's assuming your compiler supports a 64 bit unsigned type (relatively few systems support larger types than that natively).
I agree with you a loop is the best way to do it .... if you actually must do it.
In general, it is a rare real-world program that genuinely needs to compute factorial of a large integer. Most times when I see people asking how to compute a factorial, it is because of a lack of thought. For example, computing x^n/n! (where ^ represents power, for sake of discussion here) requires neither the computation of x^n nor n! as intermediate steps. The computation of n! overflows quite quickly, and the computation of x^n will overflow fairly quickly if x > 1 or underflow if x < 1. Computing them as intermediate steps is a really bad idea. With a little thought it is possible to compute the end result with a much smaller risk of overflow or underflow. For example;
Code:
// compute x^n/n!
for (i = 1; i <= n; ++i)
{
result *= x;
result /= i;
}
avoids computing a power of x directly, avoids computing a factorial, and successfully computes x^n/n! for much larger values of x or n. The risks of overflow or underflow are not eliminated, but they are reduced.
So my view is that the original question is, more than likely, the wrong question due to lack of thought.
If your program genuinely needs to compute factorials of largish values (and, as noted above, relatively few programs truly do in the real world) then you will need to use some unbounded integral representation. There are libraries for such things around.
(Double) Factorial function efficiency
