Better implementation of recip for Ratio a

[daniel.is.fischer]

Proposal: A better implementation of recip for Ratio a

Discussion period: Three weeks, until 15^th October 2010

Currently, in GHC.Real,

    recip (x:%y)        =  y % x

calculates the gcd of numerator and denominator, although they are known to be coprime (unless the constructor has been directly [ab]used or the value has been obtained via the broken fromRational, #4335). Since integer division is slow, that is an expensive operation. I propose changing recip to

    recip (0:%_)        = error "Ratio.%: zero denominator"
    recip (x:%y)
        | x < 0         = negate y :% negate x
        | otherwise     = y :% x

For all legitimate values of Ratio a with a reasonable Integral a, both implementations yield the same result.

The attached programme shows that for Rationals with large numerators and denominators, the speedup is huge:

$ ./benchRecip 40000 0
4011866
id took 1.420088s
4011833
frecip took 1.220077s
4011833
recip took 137.500593s

(id takes longer than frecip because it incudes the time to build the fibQuots list).

[daniel.is.fischer]

patch for faster recip for Ratio a

[daniel.is.fischer]

Discussion thread:  http://haskell.org/pipermail/libraries/2010-September/014429.html Supported by Felipe Lessa, no objections were raised.

Patch validated, please review and merge.

[simonmar]

Applied, thanks!

Thu Oct 21 02:32:46 PDT 2010  Daniel Fischer <daniel.is.fischer@web.de>
  * FIX #4336
  Avoid superfluous gcd calculation in recip for Ratio a because numerator
  and denominator are known to be coprime.

[igloo]

Merged.