#4336: Better implementation of recip for Ratio a
----------------------------------+-----------------------------------------
Reporter: daniel.is.fischer | Owner:
Type: proposal | Status: new
Priority: normal | Component: libraries/base
Version: 6.12.3 | Keywords:
Testcase: | Blockedby:
Os: Unknown/Multiple | Blocking:
Architecture: Unknown/Multiple | Failure: None/Unknown
----------------------------------+-----------------------------------------
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).
--
Ticket URL: <http://hackage.haskell.org/trac/ghc/ticket/4336>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler
_______________________________________________
Glasgow-haskell-bugs mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
