What algorithms exist to quickly compute the inverse factorial?

Question

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.

Answer 1

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.

Answer 2

If $n$ is the number of digits in $x!$ then $$n=\lfloor\log_{10} x!\rfloor +1\approx \frac{1}{\ln 10}\sum_{k=1}^x \ln k \approx \frac{1}{\ln 10} \int_1^x \ln t \; dt \approx \frac{x\ln x-x}{\ln 10}.$$

Say $x!$ has 2568 digits. I solve $2568 =(x \ln x-x)/\ln 10$ (by some method) to get $x=1000.764785$. I conclude $x=1000$, because most of what I discarded was negative. Sorry it's a little hand-wavy.