A runcible nonce

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.

Of Sets and bitmaps

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.

The Great Sultan of the Indies

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

Walk Count like an Egyptian (Part I)

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 ?

Fractional Bits (Part II)

In a previous post, we started discussing the subject of encoding values using fractional bits. This is quite counter-intuitive as we usually think that encoding asks for whole bits, furthermore that we think of bits as being essentially atomic—unsplittable.

However, bits can be fractioned, helping us devising efficient encodings, something not unlike a primitive form of arithmetic coding, for a variety of data. Let’s consider a simple case that illustrates the principle: encoding the date.

Universal Coding (part III)

In Universal Coding (part II), we explored the idea of variable length codes that encode integers of any magnitude in bits, but the encoding requires (somewhat) complex arithmetic, and we concluded that sometimes, it’s better to use a simple code that sacrifices some coding-efficiency in exchange for machine-efficiency. Let’s now look at one of those, MIDI VLQ and how we can make it a bit better.

Dithering.

This week, let’s discuss dithering, a technique based on error diffusion used in print and computer graphics to soften the effects of harsh color quantization. There are many types of dithering (sometimes called halftoning, despite techniques not being all of the same type), some optimized for monochrome or color screen printing, some merely convenient to use in computer graphics.

When we quantize an image to a very small number of colors, all kind of artifacts appear: false contours resulting from two too different colors that aught to be smoothly faded, noticeable color changes, etc. Dithering tries to alleviate this problem by mixing colors using random-looking dot patterns, replacing color resolution by sampling aliasing. Despite the image being composed of dots of very different colors, we still perceive the color mix, and that effect, while not adding any objective quality to the image, does augment the perceived quality of the image.

SEND+MORE=MONEY

Let’s consider a rather simple puzzle:

   SEND
+  MORE
= MONEY

where each letter is assigned a value from 0 to 9. How would you solve
it?

The Speed of GCD

The subject of computing the GCD was brought up a couple of times lately, and we assumed that the straightforward divide-and-remained implementation was the most efficient. But is it?

Before writing this post, I knew of basically two versions, one due to Euclid, invented sometimes in Antiquity of course, and one that used the remainder (that is, modulo) to do basically the same thing (which can be implemented either recursively or iteratively). Turns out that there are other algorithms, for example the so-called binary GCD that tries to somewhat speed up the process by removing multiples of two. But which one is the most efficient?

Universal Coding (Part II)

Last time, we presented universal codes and two simple code. This week, let’s revisit the topic and present Elias codes, which are much better universal codes than Chaitin’s and modified Chaitin codes.

We will use the idea of recursion introduced before, but we will push the idea further, getting codes with lengths , which are pretty much as good as it gets.