[Contents]

1  Stirling’s Approximation(s) for Factorials

There are quite a few known formulas for approximating factorials and the logarithms of factorials. At least two of these are named after James Stirling: the so-called Stirling approximation should probably be called the “first” Stirling approximation, since it can be seen as the first term in the Stirling series.

Let’s begin by deriving the basic Stirling formula.

We can always expand the logarithm of N! as:

ln(N!) = ln(1) + ln(2) + ln(3) + ⋯ + ln(N)
=
 N ∑ i=1
ln(i)
(1)

In figure 1 and figure 2, we consider the example where N=8. In each figure, the blue area represents ln[(N−1)!]. The yellow area represents ln(N) so that the blue and yellow areas together represent ln(N!).

Figure 1: Stirling’s Approximation : Upper Bound

Figure 2: Stirling’s Approximation : Lower Bound

We can use figure 1 to obtain an upper bound on ln(N!):

ln[(N−1)!] = ln(N!) − ln(N
<
 N 1
ln(xdx
ln(N!) <
 N 1
ln(xdx + ln(N)
(2)

Similarly, we can use figure 2 to obtain a lower bound on ln(N!):

ln(N!) >
 N 1
ln(xdx
(3)

This is useful because we can easily do the integral:

 N 1
ln(xdx
=
 x ln(x) − x

 N 1

= N ln(N) − N + 1
(4)

We can always subtract 1 from the lower bound to obtain a looser lower bound. Combining results, we have:

 N ln(N) − N + 1   <   ln(N!)   <   (N+1) ln(N) − N + 1
(5)

We now switch from obtaining bounds to obtaining estimates and approximations. Some interesting approximations include:

 ln(N!) ≈ N ln(N) − N low-low, aka lame Stirling ln(N!) ≈ N ln(N) − N + 1 low ln(N!) ≈ (N+½) ln(N) − N + 1 middle ln(N!) ≈ (N+½) ln(N) − N + ½ ln(2π) first Stirling ln(N!) ≈ (N+1) ln(N) − N + 1 high
(6)

The low-low approximation can be obtained subtracting 1 from the lower bound to obtain a looser lower bound. It is sometimes called “the” Stirling approximation, but for small N it is pretty lame, and it is easy to do better. The middle approximation results from splitting the difference between the lower bound and the upper bound. The zeroth-order term in the first Stirling approximation is ½ln(2π) ≈ 0.918939. This may not seem much different from the 1 that appears in the middle approximation, but the first Stirling approximation performs noticeably better than the middle approximation. The other approximations in equation 6 are terrible by comparison ... although they are all the same to leading order, so the percentage error becomes small if N is sufficiently huge.

Other noteworthy approximations include the following. Gosper does better than first Stirling, with minimal complexity. Second Stirling does better still, with very little additional complexity.

 ln(N!) ≈ N ln(N) − N + ½ ln((2N + 1/3)π) Gosper ln(N!) ≈ (N+½) ln(N) − N + ½ ln(2π) + 1/12/N second Stirling
(7)

[Contents]