Re: Mapping rationals to binary strings while preserving order
- From: Janez Brank <sudjbran@xxxxxxxxxxxxxx>
- Date: Thu, 13 Jul 2006 12:03:16 +0200
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.
-----
Janez
.
- Follow-Ups:
- Re: Mapping rationals to binary strings while preserving order
- From: Torben Ægidius Mogensen
- Re: Mapping rationals to binary strings while preserving order
- References:
- Mapping rationals to binary strings while preserving order
- From: Janez Brank
- Mapping rationals to binary strings while preserving order
- Prev by Date: Re: Algorithm to fit rectangles with different areas inside a matrix with lowest complexity
- Next by Date: Re: Mapping rationals to binary strings while preserving order
- Previous by thread: Re: Mapping rationals to binary strings while preserving order
- Next by thread: Re: Mapping rationals to binary strings while preserving order
- Index(es):
Relevant Pages
|
