Proposal: Better power for Rational
Isaac Dupree
ml at isaac.cedarswampstudios.org
Sat Sep 25 11:05:59 EDT 2010
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
More information about the Libraries
mailing list