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

Attachments (1)

rationalPower.dpatch (52.7 KB) - added by daniel.is.fischer 9 years ago.
special versions of power functions

Download all attachments as: .zip

Change History (6)

comment:1 Changed 9 years ago by igloo

Milestone: Not GHC

Changed 9 years ago by daniel.is.fischer

Attachment: rationalPower.dpatch added

special versions of power functions

comment:2 Changed 9 years ago by daniel.is.fischer

Status: newpatch

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 simonmar

Owner: set to simonmar

comment:4 Changed 9 years ago by simonmar

Status: patchmerge

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.

comment:5 Changed 9 years ago by igloo

Resolution: fixed
Status: mergeclosed

Merged.

Note: See TracTickets for help on using tickets.