Proposal: Better power for Rational
Daniel Fischer
daniel.is.fischer at web.de
Sat Sep 25 09:36:42 EDT 2010
On Saturday 25 September 2010 14:21:10, Ian Lynagh wrote:
> On Sat, Sep 25, 2010 at 02:34:16AM +0200, Daniel Fischer wrote:
> > 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)
>
> Are you deliberately only doing this for Rational, rather than (Ratio t)
> in general, to avoid differences in behaviour of Integral types?
Yes, it would change the behaviour for general t.
Take for example t = Word8.
(17 % 3) ^ 3
= ((17 % 3) * (17 % 3)) * (17 % 3)
= (289 % 9) * (17 % 3)
-- reduce numerator mod 256
= (33 % 9) * (17 % 3)
-- reduce 33 % 9
= (11 % 3) * (17 % 3)
= (187 % 9)
(17^3) % (3^3)
= 4913 % 27
-- reduce numerator mod 256
= 49 % 27
I'm not principally against changing that behaviour, but changing the
results of functions is a big undertaking versus just improving
performance.
Either behaviour is broken as soon as overflow occurs, they're just broken
in different ways.
>
> If it was generalised, then we'd presumably want to use % for the final
> result, so that
> (2^16 / 3) ^ 2 :: Ratio Int32
> is (0 % 1) rather than (0 % 9).
I wouldn't call (%) directly, with
ratPow (x:%y) e = reduce2 (x^e) (y^e)
reduce2 = (%)
{-# RULES
"reduce2/Rational" reduce2 = (:%) :: Integer -> Integer -> Rational
#-}
We should be able to avoid the superfluous gcd for Rationals (and gcd for
Integers is far more costly than for the common fixed-width types).
>
>
> Thanks
> Ian
>
Cheers,
Daniel
More information about the Libraries
mailing list