Factorial Approximations

(and its logarithm) keep showing up in the analysis of algorithm. Unfortunately, it’s very often unwieldy, and we use approximations of (or ) to simplify things. Let’s examine a few!

First, we have the most known of these approximations, the famous “Stirling formula”:

,

Where the terms at the right are known as Stirling Series (the numerators are given by A046968 and the denominators by A046969). If you evaluate the complete series, it’s truly equal to .

However, you may not quite want to evaluate an infinite series, and we find truncated versions:

that we will call “Stirling” from now on; a “Stirling more” version could be

,

or even a “Stirling most”:

.

The literature is fraught with approximations. For example, we find Gosper’s:

.

Everybody refers [a] as the source of this approximation. However, while it can be a consequence of that paper, it’s not in it (also, its typography is a train wreck).

We have Burnside’s [2]:

.

Then Mortici’s [3]:

.

There are plenty more, but let’s consider one more. Mohanty and Rummens’ [4]:

.

*
* *

How do those compare? Asymptotically, when is very large, the ratio of any of these approximation to goes to 1. On smaller , they also all kind-of-work OK:

From the figure above, we see that Gosper’s does very well, just a bit worst than “Sterling More”. Mohanty and Rumme1ns’ does best, but it’s also quite a bit more complex than Gosper’s. What if we have a look at the digits that are output? The following shows the result (in Mathematica, which computes in “infinite precision”) rounded:

But what’s more telling, is the ratio to the real value:

But we can also have a look at the number of correct leading digits:

*
* *

So Gosper’s approximation is much better than just the truncated Stirling and compares to “Stirling More”, which is not that surprising because it’s very close to what you get by distributing the into the square root; so it’s a good numerical trade off. However, “Stirling More” and Mohanty & Rummens’ compare with a slight advantage to the later.

---

[1] R. William Gosper, Jr. — Decision Procedure for Indefinite Hypergeometric Summation — Procs. Nat. Acad. Science USA, vol 75 no 1 (1978) p. 42–46.

[2] W. Burnside — A Rapidly Convergent Series for Log N! — Messenger Math., vol 46 no ? (1917) p. 157–159

[3] Cristinel Mortici — An Ultimate Extremely Accurate Formula for Approximation of the Factorial Function — Archiv der Mathematik, vol 93 (2009) p. 37–45

[4] S. Mohanty, F. H. A. Rummens — Comment on “An Improved Analytical Approximation to n!” — J. Chem. Physics, vol 80 (1984) p. 591.