Stirling's Approximation

Do you like factorials?

Probably, you do. If no, whatever, read this post to know how get rid of factorials.

TL;DR

It is Stirling’s approximation or just Stirling’s formula. It allows to replace factorials with their approximation. If you not interested in math, skip to formula usage

Proof

Replace factorial with its definition:

Transform logarithm of multiplication to sum of logarithms:

Take a look at the integral $\int_a^b f(x) dx$ Replace $f(x)$ with $ln(x)$, $a$ with $1$, and $b$ with $n$. Then use numerical integration with step 1 and right rectangle rule

Right-hand parts of two previous formulas are equal, with respect $ln(1)=0$. Then:

Calculate integral using integration by parts:

Applying boundaries [1..n]

yields final result:

Exactly what on the top.

Developer Proof

It is much simpler proof, with lose of accuracy, but still valid for partial applications.

Replace factorial with its definition:

Transform logarithm of multiplication to sum of logarithms:

From monotonic property of logarithms $a \leq b \rightarrow ln(a) \leq ln(b)$ take upper bound for each $ln(i)$:

Then, using worst case substitution, sum can be rewritten as:

But $ln(n)$ does not depend on i, so get rid of sum:

Done.

Usage

No one cares about O(log(n!)) of your algorithm, but everybody knows that O(n log n), linearithmic complexity, is very good property of algorithm. By the way, do not scare people with factorial sign.

If you try to calculate ln(n!) with most straightforward implementation without suitable datatype, you’ll likely get the number overflow exception, in spite of result value is not very large. For example for n=100 overall result is approximately 363 (Stirling’s approximation gives 361) where factorial value is $10^{154}$.

As far as I know, calculating factorial is O(n) complexity algorithm, because we need n multiplications. Using Stirling’s approximation we need to calculate $n^n$ term, that can be calculated in O(log n) with clever trick

It can be surprising, but factorials defined not only for positive integers. So, for example 2.5! is completely valid expression. -6! also. They can be calculated using Gamma-functions for real numbers. Unfortunately, they are pretty complicated, so people use Stirling’s formula instead.

Almost everything that using factorials can use Stirling’s approximation. Permutations, binomial coefficients, fractals, number theory and a huge amount of topics I’m not aware of.

P.S. Stirling’s formula presented here is rough enough. More accurate formula is . Check its proof here.

mishadoff 23 February 2013
blog comments powered by Disqus