Re: Mapping rationals to binary strings while preserving order

On Wed, 12 Jul 2006, Herbert Glarner wrote:

You obviously are willing to deal with different bit lengths, i.e. treat
the mapped representation as a bitstream. Depending on how you plan to
store them, you might run into a practical problem there. Consider you
see a bitstream like 01011. How do you interpret it? It is ambigeous and
may signify the two fractions 01;011 or the only fraction 01011 or even
the three "fractions" 0;1;011 etc.

If you right-pad the missing bits with 0es so that all numbers are of
same length, the numbers are not ambigeous anymore, but then there is no
point in searching for shorter string representations, because it is
determined alone by the range of your fractions (if there is any, that
is). If it is a requirement to represent all possible fractions, then
you will have a large number of bits pretty soon. After all, the initial
bit is 0 for a fraction < 1, and in e.g. 15 bits you can only represent
2^15=32k different fractions.

Thus, the additional information needed before thinking about such a
representation is: Is your input finite? If so, what is the resolution
you have in mind? Is the max. denominator 9 as per your example?

Actually, I wasn't thinking of this as a practical problem, so e.g. if a
bitstream like 01011 could be interpreted as 01;011 or 01011 or 0;1;011
that doesn't really bother me. Nor was I thinking about having any limits
regarding the size of the denominator -- I would be interested in a
function f that works on any rational number between 0 and 1, regardless
of its denominator. I realize that eventually a large number of bits
is required, but what I'm wondering is how quickly this required number of
bits grows as a function of v -- the construction in my original post
required O(v) bits, and I'm wondering if a sublinear number of bits would
also be sufficient.

-----
Janez

.

Relevant Pages

  • Re: Mapping rationals to binary strings while preserving order
    ... the mapped representation as a bitstream. ... may signify the two fractions 01;011 or the only fraction 01011 or even ... same length, the numbers are not ambigeous anymore, but then there is no ...
    (comp.theory)
  • Re: Mapping rationals to binary strings while preserving order
    ... You obviously are willing to deal with different bit lengths, i.e. treat the mapped representation as a bitstream. ... If you right-pad the missing bits with 0es so that all numbers are of same length, the numbers are not ambigeous anymore, but then there is no point in searching for shorter string representations, because it is determined alone by the range of your fractions. ...
    (comp.theory)
  • Re: Type Question
    ... this is true of all programming languages that use floating point ... Common Lisp comes pretty close to providing that as ... Change the floating point representation. ... computationally efficient binary representation, the fractions should be ...
    (comp.lang.lisp)
  • Re: Decimal versus binary arithmetic was Re: J4 - presentation/discussion on "Future of the COBO
    ... One very good reason that pure binary representation was not used is that ... decimal fractions cannot be expressed except as a repeating ... is your meaning, Robert, then you haven't made it clear. ... 01 quotient binary pic 9v9. ...
    (comp.lang.cobol)
  • Re: need just 6 digits
    ... It is true for division of integers by powers of two in ... 1/3 does have an exact one digit representation ... NaNs and infinities, are binary fractions, each double ... digits in the fractional part from all the decimal fractions ...
    (comp.lang.java.help)