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