Factorial Approximations


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

Read the rest of this entry »

Stirling’s series


Last week, we had a look at how g++ handles tail-recursion. Turns out it does a great job. One of the example used for testing the compiler was the factorial function, n!.


We haven’t pointed it out, but the factorial function in last week’s example computed the factorial modulo the machine-size (unsigned) integer. But what if we want to have the best possible estimation?

Read the rest of this entry »