ln n!

February 23, 2016

In the course of analyzing an algorithm, I used the simplifying hypothesis that the cost function is

\displaystyle c(n)\approx\sum_{i_1}^n \lg i=\lg n!.

That expression is cumbersome but we can get a really good simplified function to use as a proxy. Let’s see how.

Read the rest of this entry »


Stirling’s series

December 2, 2014

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!.

fibolapin-bw

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 »