I'm interested in algorithms to quickly compute the inverse factorial.
I've noted that large factorials have a unique number of digits. How can I use this fact to quickly compute the factorial? Is there a formula,
n = f(n!) = #digits( (n!) )?
I'm mostly interested in the case where we know our input is correct. But, error checking for values that are not factorials would be a bonus. (Perhaps, someone has thought of a way to do the inverse gamma function quickly?)
I'm interested in inputs that have over a million digits, so simply dividing 1,2,3,…,n will not work.
Best Answer
Assuming the input is correct, one could conceivably use Stirling's approximation or higher-order asymptotic expansions of the Gamma function and then invert. In other words, using the Stirling approximation $$ n! \sim \sqrt{2 \pi n} (n/e)^n, $$ one could for example take logarithms and obtain $$ \log(n!) \sim \frac{1}{2} \log(2 \pi) + (n - 1/2) \log(n) - n, $$ and then solve the resulting nonlinear equation using bisection combined with a Newton method. This would yield a non-integer value, but assuming that the input $k = n!$ is exact, then I would expect this rounds to the correct value.