Mark Biggar wrote:
Handling promotion (and demotion) between single and multi-precision integers is fairly easy. And once you have that doing it for rationals is basically free. Likewise promoting an Integer up to rational is trivial and vice versa. But promotion (or demotion) between IEEE floats and rationals is really hard and I don't know of a language that even tries. The major problem is that the demotion from rational to IEEE float is very lossy. In general, there are many possible distinct rationals that convert into the same IEEE value and converting IEEE float to the simplest rational out of that set is a very expensive operation.. Once you're in rationals you probably never want to demote back to IEEE (except possibly at the very end). Every language that supports rationals, that I know of, leaves it up to the programmer to decide whether they will be doing computations in IEEE float or rationals and do not try to automatically convert back and forth. I looked at thos and basically gave up when I was writing the perl 5 Bigint and Bigrat packages.


Before you discuss implementations, you should define exactly what rules you are going to use for promotion and demotion between the various types.

Since conversion from a rational to a IEEE float is almost always lossy, I would say never do it automatically, and only do it when requested with an explicit type cast, such as when converting a rational to an integer.

Generally speaking, IEEE floats are always in base 2 to a fixed precision, so almost all math done with them is approximate; users pick IEEE floats over unlimited rationals because they want to trade off precision for resource efficiency.

If one receives input as an IEEE float and wants to do exact math with it for some reason, they can convert it losslessly to a rational; this conversion would also be done by explicit cast, not implicitly.

If the rational representation as a triple of integers I suggested is used, then conversion from an IEEE float is inexpensive, and can go as follows.

Say the exact triple format looks like this:

  subtype Int2_N of Int where { $^n >= 2 };

  class Rational {
    has Int    $.mantissa = 0;
    has Int2_N $.radix    = 2;
    has Int    $.exponent = 0;
  }

This format could represent a few sample numbers as follows:

  0 -> 0*2**0
  1 -> 1*2**0
  1/8 -> 1*2**-3
  0.001 -> 1*10**-3
  3.14159 -> 314159*10**-5
  4.5207196*10**30 -> 45207196*10**37
  :2<101110.1101> -> :2<1011101101>*2**-4
  :16<DEADBEEF00> -> :16<DEADBEEF>*2**8

Now in a typical 64 bit IEEE float, if I'm not mistaken there are about 53 bits for a sign plus mantissa and those bits represent N*1/2+N*1/4+... sort of like a 53 bit integer divided by 2**53; the 42 bit float then has 11 bits for a signed exponent, and a radix of 2 is implied.

So said IEEE float could be interpreted more or less as the number determined by:

  IEEEman*2**IEEEexp

... where IEEEman and IEEEexp are the conceptual values of those bit patterns of the relevant parts of the IEEE float.

Then conversion into straight integers for my representation would be:

  IEEEman*(2**53)*2**(IEEEexp-53)

Something like that, or maybe slightly more complicated.

And so, any IEEE float would convert to a rational of the format I proposed for essentially a constant amount of RAM usage regardless of what the IEEE value is; RAM usage would not increase when IEEE floats with very large numbers for exponents are converted, unlike a numerator/denominator representation.

Now, doing math with rationals of the format I propose should cost roughly the same as a numerator/denominator representation, but mine should use less RAM in the extreme cases. Your speed profile would likely depend on what normalization strategy you use. For example, if you normalize such that the exponent is always -1 then your profile should be the same as a numerator/denominator representation. By contrast, normalization for best memory use would involve using as large a number as possible in the exponent; ideally the radix would be small as possible, such as 2 or 10.

-- Darren Duncan

Reply via email to