Better implementation of recip for Ratio a
Proposal: A better implementation of
Discussion period: Three weeks, until 15^th^ October 2010
Currently, in GHC.Real,
recip (x:%y) = y % x
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 (closed)).
Since integer division is slow, that is an expensive operation.
I propose changing
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