Re: Mapping rationals to binary strings while preserving order

Janez Brank wrote:
Hello all!

Consider the following problem: we want to find a function that maps rational numbers from the range [0, 1] into binary strings.
The function f should satisfy the condition that, for any two
rational numbers x, y, 0 <= x < y <= 1, the string f(x) should be
lexicographically less than f(y).

One suitable mapping is this: for a rational number u/v, where 0 <= u <= v
and gcd(u, v) = 1, consider the sequence
floor(i u/v) - floor((i-1) u/v) for i = 1, 2, ..., v.
Each of these values is either 0 or 1, and concatenating them we get a
string of v bits. If we define f(u/v) to return this string, it can be
shown that it has the property required in the first paragraph.

For example:
fraction value string
0/ 1 0.000000 0
1/ 9 0.111111 000000001
1/ 8 0.125000 00000001
1/ 7 0.142857 0000001
1/ 6 0.166667 000001
1/ 5 0.200000 00001
2/ 9 0.222222 000010001
1/ 4 0.250000 0001
2/ 7 0.285714 0001001
1/ 3 0.333333 001
3/ 8 0.375000 00100101
2/ 5 0.400000 00101
3/ 7 0.428571 0010101
4/ 9 0.444444 001010101
1/ 2 0.500000 01
5/ 9 0.555556 010101011
4/ 7 0.571429 0101011
3/ 5 0.600000 01011
5/ 8 0.625000 01011011
2/ 3 0.666667 011
5/ 7 0.714286 0110111
3/ 4 0.750000 0111
7/ 9 0.777778 011101111
4/ 5 0.800000 01111
5/ 6 0.833333 011111
6/ 7 0.857143 0111111
7/ 8 0.875000 01111111
8/ 9 0.888889 011111111
1/ 1 1.000000 1

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

Maybe I'm not understanding the problem, but I think there's a much simpler solution. Just store your number in a standard 4 or 8 byte IEEE floating point format. The first few bits store the scale, and the rest store the most significant bits of the value. It sorts lexicographically just fine.

.

Relevant Pages

  • Re: Storing a value for later use in vba or a Macro
    ... Dim strCurrentCustomer as String ... do you programmatically store a value from one record to use in ...
    (microsoft.public.access.gettingstarted)
  • Re: Storing wave files in database
    ... analyse them and store everything in some sort of database. ... You don't store the Wave files in the database. ... ByVal lpOperation As String, _ ... Dim lRet As Long, varTaskID As Variant ...
    (microsoft.public.dotnet.framework.adonet)
  • Re: Question about a data structure
    ... I'll store the ... string, it could just be a simgle 150 character string. ... , personally, I'd avoid 'stringing' together responses. ...
    (alt.php)
  • RE: adding data to a file before it gets regexed
    ... The reasion I am trying to add the string to the line, is so that I can use ... it is not a good idea to store entire files in memory and it is really ... the arrays are the contents of the files broken down by lines. ... Any opinion expressed in this e-mail is personal to the sender ...
    (perl.beginners)
  • Re: Java Applet saving results on home server
    ... I can also store the results to a string and write that to a ... that has some data structures to store all the things I need, ... This puts you right back into your original question. ... I've got a problem with the Jakarta ftp client. ...
    (comp.lang.java.help)