Weird binomial coefficients

September 27, 2016

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?

September 20, 2016

Sometimes, you need to compute a function that’s complex, cumbersome, or which your favorite language doesn’t quite provide for. We may be interested in an exact implementation, or in a sufficiently good approximation. For the later, I often turn to Abramovitz and Stegun’s Handbook of Mathematical Function, a treasure trove of tables and approximations to hard functions. But how do they get all these approximations? The rational function approximations seemed the most mysterious of them all. Indeed, how can one come up with

$e^x \approx 1-0.9664x+0.3536x^2$

for $e^x$, for $0\leqslant x\leqslant\ln 2$?

Well, turns out, it’s hard work, but there’s a twist to it. Let’s see how it’s done!

The protoshadok number system

September 13, 2016

We’re so used to our positional notation system that we can’t really figure out how to write numbers in other systems. Most of the ancient systems are either tedious, complicated, or both. Zero, of course, plays a central role within that positional system. But is it indispensable?

In one of my classes, I discuss a lot of different numeration systems (like Egyptian, Babylonian, Roman and Greek) to explain why the positional system solves all, or at least most, of these systems’ problems. I even give the example of Shadok counting (in french) to show that the basis used isn’t that important (it still has to be greater than one, and, while not strictly necessary, preferably a positive integer). But can we write numbers in a positional system without zero?

Serializing Trees

September 6, 2016

Quite a while ago I discussed using flat arrays and address calculations to store a tree in a simple array. The trick wasn’t new (I think it’s due to Williams, 1964 [1]), but is only really practical when we consider heaps, or otherwise very well balanced trees. If you have a misshapen tree, that trick doesn’t help you. It doesn’t help you either if you try to serialize a misshapen tree to disk.

But what if we do want to serialize arbitrarily-shaped trees to disk? Is it painful? Fortunately, no! Let’s see how.