3 ms·
The XKCD book page numbering explained (or skew binary explained)
- eru 17y agoOkasaki 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.
- icefox 17y agoThe 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.
- eru 17y agoThe first 10 numbers in skew binary are 0, 1, 2, 10, 11, 12, 20, 100, 101, and 102.
- selven 17y agoThe 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.
- eru 17y agoIndeed. And related to efficient data structures.
- bmalicoat 17y agoThat 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?