Proposal: Better power for Rational

[Isaac Dupree]

On 09/24/10 20:34, Daniel Fischer wrote:
> Proposal: A better implementation of powers for Rational

generally +1

> For well-formed Rationals, the numerator and denominator are known to be
> coprime, hence all powers of the numerator and denominator are also
> coprime.

Is it worth putting this stuff in the Data.Ratio code comments to 
explain why what you're doing is valid and useful, or is it already 
well-commented enough in a general sense about why "gcd" is sometimes 
necessary, yet expensive?

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

Can you do the same for ^^ ? That is, a ratPowCanBeNegative (implement 
in terms of ratPow, or directly, as you please) and a RULE.

(better names would be good if these are going to be exported though! 
But I don't think they need to be exported, unless hmm, is removing 
'gcd' an *asymptotic* speedup for large integers?)

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

Wondering why is there an extra case for x:%1 when the x:%y case handles 
that correctly (albeit slower)?  Integer-base ^ does not have this 
1-base optimization (maybe that's just because '1' maybe isn't 
multiplicative identity for general Num, and GHC.Real.^ is written for 
general Num base, or 1-base isn't common for general exponentiation but 
in Rationals it's common to have a Rational that's a whole number?), and 
you don't test for 1-base numerator.  I think your choice is sensible 
enough overall; would like to hear what you think.

> Like the elimination of `gcd` from recip (#4336), this would yield a great
> performance boost.

Did you measure the performance, or is it just obvious?  (Either is okay 
with me.)

-Isaac