Better implementation of recip for Ratio a
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 (closed)).
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).
Trac metadata
Trac field | Value |
---|---|
Version | 6.12.3 |
Type | Bug |
TypeOfFailure | OtherFailure |
Priority | normal |
Resolution | Unresolved |
Component | libraries/base |
Test case | |
Differential revisions | |
BlockedBy | |
Related | |
Blocking | |
CC | |
Operating system | |
Architecture |