Better power for Rational

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 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 (closed)), this would yield a great performance boost.

Trac metadata

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