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
