The XKCD book page numbering explained (or skew binary explained)

barklund.org

17 points·prakash··8 comments

The first paragraph should have listed some of the page numbers as I don't have the book so I didn't know what he was talking about.

The first 10 numbers in skew binary are 0, 1, 2, 10, 11, 12, 20, 100, 101, and 102.

The basic pattern is that it's like trinary, but once you get to something ending in some 1s and finally a 2, the two starts to migrate upward, leaving 0s behind it (as in 10112, 10120, 10200, 11000) until the 2 disappears and you keep on going normally. The effect is that instead of digits flipping over all at once, as in 999998, 999999, 1000000, it happens one at a time. Very interesting number system.

Indeed. And related to efficient data structures.

Okasaki has a lot about skew binary numbers (and other strange systems) in his "Purely Functionaly Data Structures". Linked lists are basically equivalent to unary. Fibonacci number systems are also useful. You can also use `redundant ternary' and much more.

Even partial differentiation of (algebraic) data structures is a useful operation. It corresponds to looking at data structures with `holes' in them. The functional people call them zippers.

That article was interesting but the contrast between the paragraphs and the code blocks made my eyes strain way too much. Am I the only one?

Readability FTW, again.

http://lab.arc90.com/experiments/readability/

I sooo need a new theme, but haven't found anything worth implementing :)

Reply on news.ycombinator.com