4
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ OP: Note that this approach does not verify that the value is in fact the factorial of a positive integer. (+1 nevertheless.) $\endgroup$ – Brian Tung Oct 4 '16 at 23:28
  • $\begingroup$ I like this approach, but we still have to take the logarithm of our n factorial. This is non-trivial in practice ---- we have to input our data as an integer of very large size. Indeed, the largest long (64 bit integer) we can store (in Java) is 9223372036854775807. So, we need arbitrary size integers for this approach. $\endgroup$ – Daniel Oct 4 '16 at 23:42
  • $\begingroup$ Actually, computing logarithms is one of the cheapest things you can possibly do. Indeed, counting the number of digits in an integer is essentially taking a logarithm. Making this precise links your observation with the Stirling approximation approach. $\endgroup$ – Christopher A. Wong Oct 5 '16 at 2:12
  • $\begingroup$ You're right! The main issue is there's no built in methods for log on arbitrary precision integers (BigInt) in Java. So, I'd have to whip up my own. It would be possible and would be efficient but time is also of the essence. This question was originally part of a programming competition (with ten questions total) intended to be solved in 5 hours. $\endgroup$ – Daniel Oct 5 '16 at 3:17
  • 1
    $\begingroup$ It doesn't matter how big the integer is, we don't need to compute a logarithm with such great precision. Suppose, for example, we could only compute logarithms of numbers from $1$ to $10$. But we need to compute $\log_{10}$ of $160$. But $160 = 1.6 \times 100$, so it's the same as $2 + \log_{10}(1.6)$ $\endgroup$ – Christopher A. Wong Oct 5 '16 at 3:26
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Would you mind explaining/linking how this formula was described? Thanks! $\endgroup$ – Daniel Oct 5 '16 at 3:21
  • $\begingroup$ @Daniel The chain of (almost) equalities is the derivation. Is there one that in particular that's troubling? $\endgroup$ – B. Goddard Oct 5 '16 at 3:58
  • $\begingroup$ The integral one to the very last one. $\endgroup$ – Daniel Oct 5 '16 at 12:28
  • $\begingroup$ I got the integral by applying (a simple version) of the Euler-Maclauren sum formula. I was sloppy, in rounding without thinking carefully, but I think those things can be fixed up. A good, elementary version of E-M is in Tom Apostol's Analytic Number Theory, page 54. tinyurl.com/gqhevjx. The integral evaluates easily with integration by parts. $\endgroup$ – B. Goddard Oct 5 '16 at 19:05
0
$\begingroup$

If you know French, I have posted an elementary algorithm on: https://fr.quora.com/Comment-puis-je-r%C3%A9soudre-x-40320-math%C3%A9matiquement

If you don't, use the following version of Stirling's formula (six terms): ln x! = x F (x), où F (x) = ln (x) -1 + (0,5 ln x + 0,921894) / x + 1/(12 n^2) – 1/(360 n^4)

Therefore: x = log (x!) / F (x), which suggests the obvious iteration: x(i) = log(x !)/ F(x(i-1)) An elementary computer programme can be easily contrived. F(0) can be practically anything, I normally use 10.

Just for fun, try with ln(x!)= 1.281551838 *10^7 [ln(x!) has 5.5 million figures]. F(0) can be 10. In ten iterations you find x, with three decimal figures, which obvioulsy are useless for an integer.

The advantage of this algorithm is that you do not need to input the factorial itself, but its natural logarithm, a much smaller number.
Hope it helps.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.