Proposal: Make gcd total

[Daniel Fischer]

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.