#4337: Better power for Rational
----------------------------------+-----------------------------------------
Reporter: daniel.is.fischer | Owner:
Type: proposal | Status: new
Priority: normal | Component: libraries/base
Version: 6.12.3 | Keywords: Rational, power, performance
Testcase: | Blockedby:
Os: Unknown/Multiple | Blocking:
Architecture: Unknown/Multiple | Failure: Runtime performance bug
----------------------------------+-----------------------------------------
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.
--
Ticket URL: <http://hackage.haskell.org/trac/ghc/ticket/4337>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler
_______________________________________________
Glasgow-haskell-bugs mailing list
Glasgow-haskell-bugs@haskell.org
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
