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.

El corte de Leones

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 . But, well, is it true?

In this week’s entry, let us first see what geometry 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)

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!

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: .

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

Numerological Transform

I was reading Les jeux et les hommes (the original of Man, Play and Games, [wikipedia] [Amazon.com] and Caillois (the author) makes a remark about numerology. First, he discredits it as merely superstitious (on which I agree totally), but he then makes the remark that the “numerological transform”, this operation that consists in adding the digits of a number repeatedly until only one digit is obtained is uniform over all numbers. Does that makes intuitively sense? Well, we can at least verify it experimentally first!

First, let’s write a short program to generate the raw data. This time, I’ll use Mathematica because it’ll be easier to plot the results. The procedure is as follows:

Universal Coding (Part I)

It’s been a while since I last talked about data compression. Let us return to the topic this week with universal codes. Universal codes are entropy-like codes, but, unlike, say, Huffman codes, they presuppose very little on the distribution of the integers to code.

We can use optimally a universal code for a random variable if

• all integers may show up: , ,
• and if beyond , the distribution is non-increasing, that is, for and , , we have .

We will show how to build an universal code in a moment, but we will first state the condition that makes a code universal if the probability distribution satisfies the above condition. A code with length function (the length of the code for the integer ) is -universal if, and only if

That is, the expectation of the length (in bits) of the code is proportional to the logarithm of the number being coded.

Let’s now see what an universal code looks like

Euclid, Primes numbers, and a Bit of Algorithm Analysis (Part IV)

While we looked at using the GCD for devising a Las Vegas-type algorithm to test for the primality of a number in a previous entry, we saw that actually testing the number against a list of primes (therefore assuming we have an arbitrarily long list of primes), one prime at a time, is much faster.

The GCD method, for divisor , tests a number in steps, but we haven’t determined the complexity of the other method. Let’s do that now.

Hash Table and Magic (Relatively Primes) Numbers

Today, let’s talk about hash tables. Or, more precisely, one type of secondary probing technique, one that uses some number theory—but not quadratic residues, just relatively prime numbers.

I don’t know if you’re like me, but it often bugs me when I read something in a textbook that seems to make sense, but is claimed without proof nor demonstration (oh, I think I said that before). That seems to happen particularly often when I read stuff about data structures, and this time I decided to explore one of those claims.

Amicable Numbers (Part II)

In the first part we discussed how to compute the sum of proper divisors function from the sum of divisors function, . We saw that if we factorize the number then compute the list divisors from prime factor, it was much faster (on average) than testing each possible numbers from to (or , since we get one large divisor for every small divisors).

So now, let’s all put that together to get an efficient program that enumerates amicable pairs. First, we obtain a list of primes (not missing any) where the largest prime is , the largest number we will be testing—we need it to compute (up to) . If we were to search for all amicable numbers, the list would need to be unbounded, maybe we would need to produce it as we go along; but if we look for amicable pairs up to, say, about , we only need primes up to (and there’sn’t that many of them). For the sake of efficiency, we also need a way of not testing a number twice.

The Sieve of Eratosthenes

The Ancient Greeks never fail to amaze me. Sometimes their ideas border the merely superstitious, sometimes you find a guy like Eratosthenes (c. 275 BC – c. 195 BC) that comes up with a truly modern idea. I’m not talking about his invention of geography (in the modern sense of the word) nor about his suspiciously accurate estimate of Earth’s size. No, I’m talking about an algorithm that has a very modern feel to it: the sieve of Eratosthenes

So what is it that I find so modern about this algorithm? Well, it has a computational feel to it, replacing smarts with a simple procedure, regular and repetitive. So, how hard is Eratosthenes’ sieve to implement? Not every: about 10 lines of code is needed in C++ (and possibly quite fewer if we use some other language).