So I was wondering how we approximate the inverse of the Gamma function, where I tried a few methods:
Lagrange inversion theorem:
$$\Gamma^{-1}(z)=a+\sum_{n=1}^{\infty}\lim_{w\to a}\frac{(z-\Gamma(a))^n}{\Gamma(n+1)}\frac{d^{n-1}}{dw^{n-1}}\left(\frac{w-a}{\Gamma(w)-\Gamma(a)}\right)^n$$
I also found that one could find the inverse of Stirling's approximation using the Lambert W function.
And of course, there are other ones, but which method gets the most accuracy for possibly easier calculations?
Best Answer
Factorial inverse approximation is given by this formula split into couple of steps for simplicity
$$m=\frac{\ln(x)}{\ln(\ln(x)+1)} $$
$$k=\frac{\ln(\frac{m!}{x})}{\ln(m+1)}$$
$$x¡=m-k+\frac{\ln(\frac{x}{(m-k)!})}{\ln(m-k+1)}$$
Integer version
$$m=\left \lceil \frac{\ln(x)}{\ln(\ln(x)+1)} \right \rceil$$
$$k= \frac{\ln(\frac{m!}{x})}{\ln(m+1)}$$
$$x¡=\left \lfloor m-k+ \frac{\ln(\frac{x}{(m-k)!})}{\ln(m-k+1)} \right \rceil$$
(Mind the ceiling/floor marking, the last is round off, first ceiling is for better convergence only and not to have to calculate non-integer factorial twice.)
The idea is to reach $y$ from $x=y!$ as close as possible using $\frac{\ln(x)}{\ln(\ln(x)+1)}$ then, since this is undershooting, to estimate how low we are and how many times we need to multiply by $(m+1)(m+2)...(m+k)$ more, rounding this by $(m+1)^k$ since the numbers are close, finally assuming we are close enough using the estimation $(n+\epsilon)! \sim n!(n+1)^{\epsilon}$ from Gamma limit we get to the final result.
(We marked inverse factorial with inverse exclamation mark.)
The formula works for $x>1$, however, simple $\frac{(x+1)!}{x+1}=x!$ can shift it upwards.
The main advantage is that the method is giving quite a precise evaluation even for non-integer values already, certainly sufficiently for integer factorial even beyond $10^7!$. However if a better precision is needed it is sufficient to repeat the last step
$$r+\frac{\ln(\frac{x}{r!})}{\ln(r+1)}$$
It could be some special task that would require repeating this more than once, likely for small values but the step can be repeated as many times as needed.
High precision version
$$m=\frac{\ln(x)}{\ln(\ln(x)+1)} $$
$$k=\frac{\ln(\frac{m!}{x})}{\ln(m+1)}$$
$$r=m-k+\frac{\ln(\frac{x}{(m-k)!})}{\ln(m-k+\frac{1}{2})}$$
$$x¡=r+\frac{\ln(\frac{x}{r!})}{\ln(r+\frac{1}{2})}$$
Integer binary algorithm
Assume that we have integer input $x=n!$
4.a. If 4. is to be implemented in form of a loop, instead of the above, we can start dividing $w$ with $t+1$, $w_1=\frac{w}{t+1}$. We keep on dividing $w_k=\frac{w_{k-1}}{t+k}$ until reach 1. The result is the highest $t+k$ we have reached.