Proposal: Better power for Rational
Daniel Fischer
daniel.is.fischer at web.de
Fri Sep 24 20:34:16 EDT 2010
Proposal: A better implementation of powers for Rational
Discussion period: Three weeks, until 16^th^ October 2010 (ICFP again)
Exponentiation by repeated squaring, as is used in (^) is bad for Rational
since on each multiplication a gcd has to be calculated.
For well-formed Rationals, the numerator and denominator are known to be
coprime, hence all powers of the numerator and denominator are also
coprime.
To avoid superfluous work, I propose a special power function for Rationals
and a rewrite rule to replace calls to (^) for Rational bases by the
special function. It might also be beneficial to export the specialised
function from Data.Ratio to be used if the rule doesn't fire.
Proposed function and rule:
ratPow :: Integral a => Rational -> a -> Rational
ratPow _ e
| e < 0 = error "Negative exponent"
ratPow _ 0 = 1 :% 1
ratPow r 1 = r
ratPow (0:%y) _ = 0 :% 1
ratPow (x:%1) e = (x^e) :% 1
ratPow (x:%y) e = (x^e) :% (y^e)
{-# RULES
"power/Rational" (^) = ratPow
#-}
Like the elimination of `gcd` from recip (#4336), this would yield a great
performance boost.
Cheers,
Daniel
More information about the Libraries
mailing list