id,summary,reporter,owner,description,type,status,priority,milestone,component,version,resolution,keywords,cc,os,architecture,failure,difficulty,testcase,blockedby,blocking,related
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,,,,,