id,summary,reporter,owner,description,type,status,priority,milestone,component,version,resolution,keywords,cc,os,architecture,failure,testcase,blockedby,blocking,related,differential
4337,Better power for Rational,daniel.is.fischer,simonmar,"Proposal: A better implementation of powers for Rational
Discussion period: Three weeks, until 16^th^ October 2010
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 `Rational`s, 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 `Rational`s 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.
",proposal,closed,normal,Not GHC,libraries/base,6.12.3,fixed,"Rational, power, performance",,Unknown/Multiple,Unknown/Multiple,Runtime performance bug,,,,,