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 »

Weird binomial coefficients


The binomial coefficients find great many uses in combinatorics, but also in calculus. The usual way we understand the binomial coefficients is

\displaystyle \binom{n}{k}=\frac{n!}{k!(n-k)!},

where n and k are integers. But what do you do with \displaystyle \binom{\frac{1}{2}}{k}?! Is it even defined?

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 »

Computing Binomials (Part I)


We often start thinking about something, make some progress, and eventually realize it’s not going anywhere, or, anyway, the results aren’t very phrasmotic—certainly not what you hoped for. Well, this week’s post is one of those experiments.


So I was wondering, how can I compute the binomial coefficient, \binom{n}{k}, and minimize the size of the integers involved?

Read the rest of this entry »

Is Python Slow? (Part II)


In a previous post I expressed my worries about Python being excruciatingly slow and I used a toy problem to compare the speed of Python to programs in other several languages, including C.

Of course, all kind of people complained that I couldn’t compare a dynamic, interpreted language with static, compiled languages. First, let met tell you that I sure can. First, the goal was to measure speed, and not the effects of type system of the language (although logically correlated) nor the programming paradigm: the amount of CPU used to solve a given problem was the primary (if not only) point in interest.

But to be fair to Python, I extended the tests to other interpreted, dynamic languages, such as Lua, Perl, PHP and JavaScript. I also added Pascal and Haskell in the compiled languages groups.

Read the rest of this entry »