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.
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.
What delicious lunch hides in the equation
Rearrange the equation to find out!
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.
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 »
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.
The strangest aspect of the Ancient Egyptian’s limited mathematics is how they wrote fractions. For example, they could not write outright, they wrote
and this method of writing fractions lead to absurdly complicated solutions to trivial problems—at least, trivial when you can write a vulgar fraction such as . But how much more complicated is it to write rather than ?