34
$\begingroup$

Stirling approximation to a factorial is $$ n! \sim \sqrt{2 \pi n} \left(\frac{n}{e}\right)^n. $$

I wonder what benefit can be got from it?

From computational perspective (I admit I don't know too much about how each arithmetic operation is implemented and which is cheaper than which), a factorial $n!$ contains $n-1$ multiplications. In Stirling's approximation, one also has to compute one division and $n$ multiplications for $\left(\frac{n}{e}\right)^n$, no? Plus two multiplication and one square root for $\sqrt{2 \pi n}$, how does the approximation reduce computation?

There may be considerations from other perspectives. I also would like to know. Please point out your perspective if you can.

Added: For purpose of simplifying analysis by Stirling's approximation, for example, the reply by user1729, my concern is that it is an approximation after all, and even if the approximating expression converges, don't we need to show that the original expression also converges and converges to the same thing as its approximation converges to?

Thanks and regards!

  • 13
    Well, you can actually calculate $n^{n}$ in $O(\log n)$ multiplications. And if you are interested in $\log(n!)$ instead (as one often is), Stirling's approximation reduces a calculation of $n$ logarithms ($\log n + \log(n-1) + \dots$) to just one ($(n+1/2)\log n - n + O(1)$).2012-01-11
  • 0
    @mjqxxxx: Thanks! (1) How can we calculate $n^n$ in $O(\log n)$ multiplications? (2) Is calculating one logarithm more complicated than doing the corresponding exponential? (3) Is taking square root more complicated than taking square?2012-01-11
  • 6
    Approximations can be used in lots of ways. In particular, it makes it easier to compare $n!$ to other functions, to compute limits, etc. And, as others have noted, you don't need to do $n$ multiplications to compute $(\frac{n}{e})^n$.2012-01-11
  • 2
    @Tim Computing one logarithm is much more expensive. You wouldn't use Stirling's formula to estimate $6!$ You would use it to estimate $1,000,000!$ In this case, calculating the logarithm is gonna be much faster.2012-01-11
  • 1
    For a simple application, consider the number of keys for a substitution cypher, which is 26!. Since $26 \approx 10e, (\frac{26}e)^{26}\approx 10^{26}$ or about 87 bits (as $10^{27}$ would be 90 bits) and to this level we don't care about the square root part.2012-01-11
  • 1
    Even without using logarithms, you can compute $a^n$ using on the order of $\log n$ multiplications. See: http://en.wikipedia.org/wiki/Exponentiation_by_squaring2012-01-11
  • 0
    So far I don't see anyone else mentioning that Abraham Demoivre discovered this formula, nor saying what he used it for. See my answer below.2012-01-11
  • 0
    @ThomasAndrews Past a certain point, the computational complexity of multiplying arbitrary-precision numbers becomes nontrivial.2012-01-11
  • 0
    @Random832 Sure, but we don't really care about computing an approximation with arbitrary precision. That's the nature of an approximation. But it is true that the logarithm approach is better in the long run, I just gave the "exponentiation by squaring" link in answer to one of the comments above.2012-01-12
  • 0
    @ThomasAndrews: Thanks! Have been thought about these for a while. (1) Why "the logarithm approach is better in the long run", What is "the logarithm approach"? (2) Why wouldn't I "use Stirling's formula to estimate 6! You would use it to estimate 1,000,000!"? (3) Which is "this case" in "in this case, calculating the logarithm is gonna be much faster"? What method did you refere to "calculating the logarithm"? (4) "Computing one logarithm is much more expensive." Do you mean $\log_a b$ is much more expensive than $a^c$ where $b \equiv a^c$?2012-01-13
  • 0
    This triggered a subsequent question and several exhaustive answers in [SciComp](http://scicomp.stackexchange.com/questions/679/which-is-computed-faster-ab-log-a-c-or-sqrtbc) (come visit us!). For the purposes of this discussion, a logarithm in floating-point precision is on the order of 10 times more expensive than than the equivalent multiply (both are vectorizable, though the logarithm will take more effort).2012-01-13

10 Answers 10