Proposal: Make gcd total
Daniel Fischer
daniel.is.fischer at googlemail.com
Sun May 29 16:49:08 CEST 2011
On Sunday 29 May 2011 12:54:17, Ross Paterson wrote:
> On 29 May 2011 01:21, wren ng thornton wrote:
> >On 5/28/11 8:38 AM, Daniel Fischer wrote:
> >> (By the way, non-negative, like the current positive, is not entirely
> >> true, for bounded signed integer types [with twos' complement
> >> representation], gcd minBound minBound = gcd minBound 0 = minBound<
> >> 0,
> >> should that special case be mentioned or should we ignore it like we
> >> currently do?)
> >
> > That's a sticky issue, but one that needs to be documented. Given that
> > the result is always positive with the exception of gcd 0 0, gcd
> > minBound minBound, gcd minBound 0, and gcd 0 minBound, I think these
> > corner cases should be specifically enumerated.
>
> There is a difference: gcd 0 0 follows from a general rule, but the
> minBound ones are the sort of corner wierdness we get for using
> fixed-size types. (That is, the former should be mentioned as a
> non-obvious consequence, the latter as an exception/bug.)
Right.
> Incidentally,
> gcd (minBound::Int) n currently gives negative results for quite a few
> values of n.
>
Unless GHC's rewriter kicks in, which rewrites gcd :: Int -> Int -> Int to
use GMP's gcd on Integer, in which case only the cases
gcd x y = ±minBound
produce a negative result with the final fromIntegral (another instance of
optimisations changing the behaviour and producing 'better' results than
the unoptimised version).
Unfortunately, there are no rewrite rules for Int8, ..., Int64, so you'll
always get lots of negative results for gcd minBound n on those types.
Probably we should change
gcd x y = gcd' (abs x) (abs y)
to
gcd x y = abs (gcd' (abs x) (abs y))
or
gcd x y = abs (gcd' x y)
to reduce the negative results to those cases where the positive gcd cannot
be represented by the type in question.
More information about the Libraries
mailing list