id,summary,reporter,owner,description,type,status,priority,milestone,component,version,resolution,keywords,cc,os,architecture,failure,difficulty,testcase,blockedby,blocking,related
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,,,,,