Math Break: Packing

The simultaneous curse and blessing of doing mostly administration is that I don't have much time to do research, but on the other hand feel like I can study whatever interests me without worrying about the implications for annual review. As a consequence I feel like a complete idiot, trying to work on a problem that I don't know enough about yet. But it's fun.

So last night I was working through a textbook on computation analysis, trying to figure out if there can be anything like a continuous language, where a small error in the wording necessarily creates only a small effect on the meaning. In plodding through the basics of this discipline, which is new to me, I came across this little gem.

The Cantor pairing function takes two numbers and mashes them together into one. This is no big trick, you might think, since you could take x and y and add them to get one number: x + y. Yes, but in Cantor's version, the process is reversible: knowing the one number we can work backwards to recover the original two. You might think about how you would approach this.

When I explained this to my wife, she just got annoyed. "Why not just put a comma between the two numbers?" Well, for some situations, that won't work. Suppose you only have ones and zeros to work with, for example (she just rolled her eyes at that and made some disparaging comment about binary-obsessive disorder).

I came across this problem years ago when I was trying to find best case data compression estimates. Often you want to store a dictionary as efficiently as possible, and no you can't use commas. My solution was very complicated, but efficient in terms of storage.

One solution I saw in a book on complexity (in binary, of course) is to preface a number with its length as a string of ones, terminated by a zero. So if I wanted to store the number x=20, which is 10100 in binary = five bits, followed by the number y=12 (1100) you could encode:

111110101001100

With the implied dividers inserted as dashes, it looks like:

111110-10100-1100, or (length of first number)-(first number)-(second number)

So you see how you can decode the bit string to retrieve the original numbers. To me this is not aesthetic. In fact, it's ugly.

Cantor's solution to the problem is to use an arithmetic formula. Given the two numbers x and y that you want to pack together, compute this:

y + (x+y)(x+y+1)/2

My first thought was "how the heck can that work?" Can you really recapture the two numbers once you've mangled them up like that? I puzzled on it subconsciously as I read my new book on programming in perl last night, and figured it out about midnight. The key is a pattern that you might learn in a first calculus course.

The larger point is that the distinction I often make between analytical and creative is useful, and illustrated here. Anyone who was familiar enough with the right mathematical patterns would have the "lego blocks" required to assemble an explanation. Without those analytical tools, it would be hopeless.

Here's the trick. When you add up numbers in a row, like 1+2+3+...+n, you can calculate it with a formula: n(n+1)/2 instead of actually adding them all up. Notice the similarity to the right side of Cantor's formula? These are sometimes called triangular numbers because if you draw the sum as dots, you can stack them up to make a triangle. The wiki page is here. The first few triangular numbers are: 1, 3, 6, 10, 15, 21, 28, 36, 45, 55. Note that there is a pattern here: the difference between the first two is 2, the next two is 3, and so on. Let's take 45, for example--it has n = 9. If we add 10 we get the next number.

In Cantor's formula, we always get a triangular number with "base of the triangle" being x + y plus some extra bit y. The next biggest triangular number is x + y + 1 more. So in the formula, when we compute the triangular number and then add y to it, this isn't enough to get to the next biggest triangular number. This tells us how to decode it.

Example. We'll encode 4 and 5 as 5 + (4+5)(4+5+1)/2, according to the formula. That's 50. Now let's imagine we only have the 50 and we want to decode it back into two numbers. We know that it's a triangular number plus a little bit. Which one could it be?

We could just look on the list above and see that it's 45, with 5 left over, but in general we'll want to solve for it. Since 50 is a little more than n(n+1)/2 for some n, solving for n gives us the quadratic equation n*n +n -100 = 0. We can use the quadratic formula, or be lazy and look it up on Wolfram Alpha:

The mathematics engine won't stoop to doing the actual calculation, so I had to pull up the calculator to find n = 9.51... . So it's the 9th triangular number plus some change. That's 9*(9+1)/2 = 45 plus change. Hmm. That means the change has to be five, since the total is 50. Since the additional bit (the "change") is the value of y, we can subtract from nine to get x, and we're done: the original numbers are 4 and 5 in that order. I didn't mention it earlier, but it's obviously important that the order of the two numbers be preserved as well as their values.

Mathematicians like nothing so much as a whomping good generalization, so if we iterate this Cantor packing algorithm, we can squish as many numbers as we want into a single integer, just by repeating the process over and over. In order to reconstruct the original sequence, we'd only need to know how many times to apply the decoder, so we'll put that information in there too!

To pack the sequence (2,3,4,5), using the notation <x,y> to mean the packing algorithm:

1. compute <2,3> = 18
2. compute <18,4> = 257
3. compute <257,5> = 34458
4. now encode the fact that there are four numbers in our list: compute <34458,4>
   

This is easy to do on a spreadsheet:
So now you can happily send off 593831957 to someone who knows your encoding scheme, confident that they can reconstruct (2,3,4,5) from it. Or, you could just use commas.