I don’t understand what the statement of this theorem is. I can’t come up with a simple argument in my head for why there can never be enough information, but I’m not really sure how to think about it and I didn’t try very hard.
Think about bisection of ordering state space for every insert.
If 64 bits represent an ordering, and you split it in two for each insert - necessarily, to permit future insertion on either side of the new insert - then at least one side has no more than 63 bits left to store its ordering information for all future inserts on its side. You can't avoid this even with tricks that represent fractional bits.
The problem is that in order to avoid renumbering (which redistributes ordering state), the bisection needs to pre-allocate state space for future ordering information. The best it can do (without having more information about future insert order) is to split the state space perfectly evenly.
In the article, there's a big blue Update box which mentions a sequence of L/R path flips which make the fraction into a Fibonacci sequence, where you can go to 46 in sequence before exceeding a 32-bit integer. You'll observe than 46 is less than 64.
Yes, exactly this. Though it might be cleaner if instead of "no more than 63 bits" we say "no more than 2^63 spaces" on one side of the insert.
The author thinks it's very elegant that the rational numbers can be represented as a binary tree, and proposes some tricks to make the binary tree almost balanced and to make traversing it easy. You know what set is by default represented as a perfectly balanced binary tree where each bit in the representation tells you which way to go in the tree? The 64-bit integers.
Comments
I don’t understand what the statement of this theorem is. I can’t come up with a simple argument in my head for why there can never be enough information, but I’m not really sure how to think about it and I didn’t try very hard.
Think about bisection of ordering state space for every insert.
If 64 bits represent an ordering, and you split it in two for each insert - necessarily, to permit future insertion on either side of the new insert - then at least one side has no more than 63 bits left to store its ordering information for all future inserts on its side. You can't avoid this even with tricks that represent fractional bits.
The problem is that in order to avoid renumbering (which redistributes ordering state), the bisection needs to pre-allocate state space for future ordering information. The best it can do (without having more information about future insert order) is to split the state space perfectly evenly.
In the article, there's a big blue Update box which mentions a sequence of L/R path flips which make the fraction into a Fibonacci sequence, where you can go to 46 in sequence before exceeding a 32-bit integer. You'll observe than 46 is less than 64.
Yes, exactly this. Though it might be cleaner if instead of "no more than 63 bits" we say "no more than 2^63 spaces" on one side of the insert.
The author thinks it's very elegant that the rational numbers can be represented as a binary tree, and proposes some tricks to make the binary tree almost balanced and to make traversing it easy. You know what set is by default represented as a perfectly balanced binary tree where each bit in the representation tells you which way to go in the tree? The 64-bit integers.