Ticket #4336 (closed proposal: fixed)
Better implementation of recip for Ratio a
|Reported by:||daniel.is.fischer||Owned by:||simonmar|
|Keywords:||recip, Ratio, performance||Cc:|
|Type of failure:||None/Unknown||Difficulty:|
|Test Case:||Blocked By:|
Proposal: A better implementation of recip for Ratio a
Discussion period: Three weeks, until 15th 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).