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. 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?

Regards
//Herbert

--
http://herbert.wikispaces.com
.

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
    ... the mapped representation as a bitstream. ... may signify the two fractions 01;011 or the only fraction 01011 or even ... Is the max. denominator 9 as per your example? ...
    (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)