Better toRational for Float and Double

The implementation of toRational in the Real instances of Float and Double is less than ideal.

instance  Real Float  where
    toRational x        =  (m%1)*(b%1)^^n
                           where (m,n) = decodeFloat x
                                 b     = floatRadix  x

The propsed implementation of powers for Rationals (#4337 (closed)) would (when (^^) is included) alone yield a great boost, but here we can do even better.

I have benchmarked three versions of toRational against the current implementation, first, an inlined version of the proposed power modification:

{-# SPECIALISE toRat :: Float -> Rational,
                        Double -> Rational #-}
toRat :: RealFloat a => a -> Rational
toRat x = case decodeFloat x of
            (m,e) -> case floatRadix x of
                        b -> if e < 0
                                then (m % (b^(negate e)))
                                else (m * b^e) :% 1

If the exponent is nonnegative, we need not reduce (even though that reduction would be comparatively cheap since the denominator is 1, it's not free).

Next, in GHC.Float there is the condition that the floatRadix be 2, hence we can eliminate the call to floatRadix and inline. That allows to skip the reduction also in some cases where the exponent is negative:

{-# SPECIALISE toRat2 :: Float -> Rational,
                         Double -> Rational #-}
toRat2 :: RealFloat a => a -> Rational
toRat2 x = case decodeFloat x of
              (m,e) | e < 0     -> if even m
                                    then m % (2 ^ (-e))
                                    else m :% (2 ^ (-e))
                    | otherwise -> (m * 2^e) :% 1

Finally, powers of 2 can be more efficiently calculated via bit-shifting and the test for evenness is usually faster as a bit-test:

{-# SPECIALISE toRat3 :: Float -> Rational,
                         Double -> Rational #-}
toRat3 :: RealFloat a => a -> Rational
toRat3 x = case decodeFloat x of
            (m,e) | e < 0     -> case 1 `shiftL` (-e) of
                                    !d -> if fromInteger m .&. (1 :: Int) == 0
                                            then m % d
                                            else m :% d
                  | otherwise -> (m `shiftL` e) :% 1

The results vary of course depending on the sample of numbers one converts, but the trend is clear:

Current:      100 ms - 123 ms
Inlined:       32 ms -  40 ms
Specialised:   25 ms -  31 ms
Shifting:      15 ms -  23 ms

Of course, the value of that is limited, the real bottleneck in realToFrac is fromRational, which raises the times for the benchmarks by about 450 ms when added instead of a dummy conversion Rational -> Float. And using realToFrac for the conversion Double -> Float, per the rewrite rule, the benchmarks are done in about 1 ms.

Trac metadata

Trac field	Value
Version	6.12.3
Type	Bug
TypeOfFailure	OtherFailure
Priority	normal
Resolution	Unresolved
Component	Compiler
Test case
Differential revisions
BlockedBy
Related
Blocking
CC
Operating system
Architecture