April 22, 2014
In a previous entry, we discussed egyptian fractions and, in particular, a greedy algorithm to convert them. We noticed that, once in a while, the greedy algorithm generates a really large denominator, despite harmless-looking fractions:

So, I had an idea to, maybe, minimize the size of the maximum denominator.

Read the rest of this entry »

Leave a Comment » | algorithms, Mathematics | Tagged: Ancient Egyptian, Egyptian fractions, number theory | Permalink

Posted by Steven Pigeon

April 15, 2014
In the recent panic surrounding the Heartbleed bug, we ask ourselves why, and how, these bugs still happen. We know that it was a preventable bug, with a simple fix, but with potentially important repercussions.

The bug is explained in non-technical (but accurate) terms here, and the patch is shown here. But that’s not what I want to talk you about. Let’s discuss the source of the problem.

Read the rest of this entry »

4 Comments | algorithms, Cryptography, hacks, programming, Zen | Tagged: heartbleed, KISS, nonce, OpenSSL, ping, runcible, Simplicity, SSL, SSL certificate | Permalink

Posted by Steven Pigeon

April 8, 2014
When we represent sets, we have many options. We can use a language-specific primitive, like `std::set<T>` (which is likely list- or tree-like in its detail), or use a bitmap that marks, for each element (and therefore assumes that there is an universal set that contains all elements) whether or not it is included in the set. Bitmaps are simple to implement (especially when one uses something like `std::vector<bool>`) but need an amount of memory proportional to the universal set, not to the actual subset you’re trying to encode.

We can also use lists, or interval lists. But which one is the most efficient? Under what conditions? Let’s have a look.

Read the rest of this entry »

Leave a Comment » | algorithms, data compression, data structures, programming | Tagged: Bitmap, dense bitmap, sets, sparse bitmap, subset, universal set | Permalink

Posted by Steven Pigeon

April 2, 2014
What delicious lunch hides in the equation

?

Rearrange the equation to find out!

Read the rest of this entry »

Leave a Comment » | Mathematics | Tagged: Cats, humor, reddit, riddle | Permalink

Posted by Steven Pigeon

April 1, 2014
If you’re a perfectionist, it’s really hard to limit the efforts you put into developing code. A part of you wants to write the *perfect code*, while another reminds you that you haven’t time for that, and you will have to settle for *good enough code*. Today’s entry is exactly this: an ambitious design that was reduced to merely OK code.

I needed to have an exporter (but no importer) to CSV format for C++. One of the first thing that came to mind is to have a variant-like hierarchy that can store arbitrary values, each specific class having its own `to_string` function, and then have some engine on top that can scan a data structure and spew it to disk as CSV. That’s ridiculously complicated—very general—but ridiculously complicated.

Read the rest of this entry »

Leave a Comment » | C-plus-plus, programming | Tagged: C, operator overloading, operators, Simplicity, stream | Permalink

Posted by Steven Pigeon

March 25, 2014
The Great Sultan of the Indies was sent by one of his viziers 99 bags of gold, each containing exactly 50 coins. Hidden somewhere in those 99 bags is a hollowed coin (indistinguishable to the naked eye from the others) containing a secret message destined to His Most Excellent Majesty. Using a simple two-pan balance, in how many weighing can you find the bag containing the lighter coin? With how many further weighing can you find the coin within the bag?

The solution of the problem is not that complicated, but depends entirely on the assumptions you make on the balance. If one supposes that the balance is large enough to pile the 99 bags in either one of its pan, and that is locked while you’re loading it, giving its reading only once you’re done loading it, the solution that comes to mind is Read the rest of this entry »

3 Comments | algorithms, Mathematics | Tagged: Balance, Great Sultan, Indies, Mathematical recreations, Recreational mathematics, Scale, The Great Sultan of the Indies, Weighing | Permalink

Posted by Steven Pigeon

March 18, 2014
Nothing too this week: how to convert a Djvu or PDF to hard black and white PDF—not shades of gray. Why would you want to do that anyway? Well, you may, like me, have a printer that has no concept of color calibration and has dreadful half-toning algorithms, resulting in unreadable text and no contrast when you print a Djvu or a PDF of a scanned book.

Read the rest of this entry »

Leave a Comment » | Bash (Shell), hacks | Tagged: black and white, convert to black and white, Djvu, half-tone, half-toning, pdf, printing | Permalink

Posted by Steven Pigeon