Opened 9 years ago
Closed 9 years ago
#4337 closed proposal (fixed)
Better power for Rational
Reported by: | daniel.is.fischer | Owned by: | simonmar |
---|---|---|---|
Priority: | normal | Milestone: | Not GHC |
Component: | libraries/base | Version: | 6.12.3 |
Keywords: | Rational, power, performance | Cc: | |
Operating System: | Unknown/Multiple | Architecture: | Unknown/Multiple |
Type of failure: | Runtime performance bug | Test Case: | |
Blocked By: | Blocking: | ||
Related Tickets: | Differential Rev(s): | ||
Wiki Page: |
Description
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.
Attachments (1)
Change History (6)
comment:1 Changed 9 years ago by
Milestone: | → Not GHC |
---|
Changed 9 years ago by
Attachment: | rationalPower.dpatch added |
---|
comment:2 Changed 9 years ago by
Status: | new → patch |
---|
Discussion thread: http://haskell.org/pipermail/libraries/2010-September/014434.html Supported by Felipe Lessa and Isaac Dupree, no objections were raised.
Patch validated, please review and merge.
comment:3 Changed 9 years ago by
Owner: | set to simonmar |
---|
comment:4 Changed 9 years ago by
Status: | patch → merge |
---|
Applied, thanks!
Mon Oct 18 17:30:30 PDT 2010 Daniel Fischer <daniel.is.fischer@web.de> * FIX #4337 Special versions for the power functions with a Rational base and rewrite rules.
special versions of power functions