Re: Mapping rationals to binary strings while preserving order

Janez Brank <sudjbran@xxxxxxxxxxxxxx> writes:

On 13 Jul 2006, [iso-8859-1] Torben Ægidius Mogensen wrote:

So, we can uniquely represent u/v by the first log(v^2) bits of the
binary expansion of u/v. This obviously preserves lexicographical
order and it uses at most 2*log(v) bits, so it is better than neleai's
solution.

Maybe I misunderstand something (I'll try to go through your proof later
today when I have more time), but
1/3 = 0.0101010101...
5/16 = 0.0101000000...
For 5/16, we have 2*log_2(v) = 2*log_2(16) = 2*4 = 8 bits, so we get
0.01010000
and for 1/3, if we use 5 bits or less, we'll get a string that is
lexicographically smaller than the string for 5/16, e.g.:
0.01010
So for v = 3, we must use at least 6 bits, but 2*log_2(3) is less than 6
-- even 2*ceiling(log(3)) is less than that.

If we use more bits, the same problem appears eventually. E.g. if we
represent 1/3 by 0.01010101, the problem occurs for
85/256 = 0.010101010000....0,
where we again have a lexicographically larger string for 85/256 than we
do for 1/3, even though 1/3 is greater than 85/256.

I see. The problem is that by throwing away a non-0 part of the
binary fraction, a number can move up in the lexicographical sequence.

So while my suggestion gives you a unique representation for each
rational, it doesn't preserve order, as I thought it would. :-(

I still think O(log(v)) should be possible, so I'll think about it for
a bit and return if I find a solution.

Torben
.