id summary reporter owner description type status priority milestone component version resolution keywords cc os architecture failure testcase blockedby blocking related differential
4336 Better implementation of recip for Ratio a daniel.is.fischer simonmar "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).
" proposal closed normal Not GHC libraries/base 6.12.3 fixed recip, Ratio, performance Unknown/Multiple Unknown/Multiple None/Unknown