Re: Mapping rationals to binary strings while preserving order

On 12 Jul 2006 neleai@xxxxxxxxx wrote:

The mapping from the previous paragraph requires a string of length v
bits to represent the fraction u/v. But if we didn't have the requirement
that x < y should imply f(x) < f(y), we know that we could represent the
fraction u/v using only O(log v) bits. So what I'm curious about is
this: can we make our strings shorter than O(v) bits and yet satisfy the
requirement that the ordering is preserved (i.e. that x < y implies
f(x) < f(y))? How would one go about looking for such a construction (or
proving that it can't be done)?

-----
Janez

I discovered construction with O(log**2 v) bits
we divide nunbers into sets that number is in set i right when its
denominator belongs to <2**i,2**i+1).
We print reprezentation of number x in set n by.
for ( i=1; i <= n ; i++ ) {
printf("%binary" , number of elements in i-th set which are <=x )
}

Let me see if I got this right: let the set
S_i = { u/v : 0 <= u <= v, 2**i <= v < 2**(i+1) }
and for a given fraction x = u/v, we look at the sets
S_0, S_1, ..., S_{floor(log_2 v)}
and for each set we record how many elements in that set are <= x.
For each set S_i, we need O(i) bits to record this number, so the
total length of the representation is O((log v)^2) bits.

That's an excellent solution, thanks!

Can you let me know your name so that I can cite you?

-----
Janez


.