Proposal: Better power for Rational

[Daniel Fischer]

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