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 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 (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 |