Proposal: Better power for Rational
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
> For well-formed Rationals, the numerator and denominator are known to be
> coprime, hence all powers of the numerator and denominator are also
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
More information about the Libraries