(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!
The binomial coefficients find great many uses in combinatorics, but also in calculus. The usual way we understand the binomial coefficients is
where and are integers. But what do you do with ?! Is it even defined?
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, .
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?
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, , and minimize the size of the integers involved?
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.