## The Speed of GCD

December 10, 2013

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)

December 3, 2013

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 $O(\lg n + \lg\lg n + \lg\lg\lg n + \cdots)$, which are pretty much as good as it gets.

## El corte de Leones

November 26, 2013

The Alhambra, in Granada, Spain, is one of the most precious treasures of architecture, and rightfully a UNESCO World Heritage Site. I had the chance of visiting it a few years ago, and I had the chance of taking tons of photos. Recently, and that’s why I’m telling you about the Alhambra, I stumble upon a couple of texts that say that the proportions of the Alhambra are somewhat all built around ratios of $\sqrt{2}$. But, well, is it true?

In this week’s entry, let us first see what geometry $\sqrt{2}$ is supposed to give us in the Alhambra, then we will look for it in the actual building, and finally, we will see that we can arrive to the same results with a much easier method.

## Breaking the Substitution Cipher (Substitution Cipher, part II)

November 19, 2013

A while ago, we had a look at a (simple) substitution cipher. Recall, this cipher proceeds by, as its name suggests, substituting one letter for another. For the cipher to be reversible, the substitution table is in fact a permutation of the alphabet. This permutation is the cipher “key”.

We surmised that frequency analysis can help us decode a message enciphered with a substitution, but that does not help us with atypical or very short messages. What if the message is somewhat skewed, say it doesn’t even have the letter E? Can we still use the (expected) letter frequencies to start decoding it? Well, maybe. Could we use some other approach? What if we had a language model that helps us decide if a tentative deciphering makes sense? Oh, right, we do have one. And since we can use it as a “fitness” function, we can apply genetic programming to find the code!

## A random Golden Ratio Appears!

November 12, 2013

Well, we all make errors once in a while, but sometimes they’re more interesting than others. So I inadvertently forgot a square in a calculation and the series suddenly started converging, to the most beautiful of convergences of all: $\phi$.

So, let’s see how I got the golden ratio to emerge from a broken algorithm.

## Enumerating 32 bits Floats

November 5, 2013

This week, let’s go back to (low level) programming, with IEEE floats. To unit test a function of float, it does not sound unreasonable to just enumerate them all. But how do we do that efficiently? Clearly f++ will not get us there.

Nor will the machine-epsilon (the std::numeric_limits::epsilon()) because this value works fine around 1, but as the value diverges from 1, the epsilon basically becomes useless. We would either need a magnitude-dependent epsilon (which the standard library does not provide) or a way of enumerating explicitly the floats in increasing or decreasing order (something also not provided by the standard library). Well, let’s see how we can do that

## The Substitution Cipher

October 29, 2013

Some time ago, we presented the Caesar Cipher, developed a simple language model that allowed us to break the cipher relatively easily. This week, we will look at (simple) substitution ciphers.

Superficially, substitution ciphers seem much stronger than Caesar’s
cipher because, rather than just using shifting of the alphabet, it uses an
arbitrary substitution, for example,