5
$\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$

3 Answers 3

Reset to default
3
$\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$
5
  • $\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
    Commented Oct 4, 2016 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
    Commented Oct 4, 2016 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
    Commented Oct 5, 2016 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
    Commented Oct 5, 2016 at 3:17
  • 2
    $\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
    Commented Oct 5, 2016 at 3:26
3
$\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$
5
  • $\begingroup$ Would you mind explaining/linking how this formula was described? Thanks! $\endgroup$
    – Daniel
    Commented Oct 5, 2016 at 3:21
  • 1
    $\begingroup$ @Daniel The chain of (almost) equalities is the derivation. Is there one that in particular that's troubling? $\endgroup$
    – B. Goddard
    Commented Oct 5, 2016 at 3:58
  • $\begingroup$ The integral one to the very last one. $\endgroup$
    – Daniel
    Commented Oct 5, 2016 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
    Commented Oct 5, 2016 at 19:05
  • $\begingroup$ @Daniel just look at the staircase that is $1/x$ at integer points (the sum is it's area) and the continuous line (integral). You can even bound the starlircase's area between to integrals (of $1/x$ and $1/(x + 1)$ with suitable boundas) an come up with a smallis range for the error. $\endgroup$
    – vonbrand
    Commented Mar 8, 2020 at 12:51
1
$\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)$, so $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 \cdot 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$
1
  • $\begingroup$ For really large $x$, the further terms in Stirling's approximation make no real difference. $\endgroup$
    – vonbrand
    Commented Mar 8, 2020 at 12:47

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .