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