# Proposal: Make gcd total

Cale Gibbard cgibbard at gmail.com
Tue May 10 01:13:33 CEST 2011

+1

On 9 May 2011 19:11, Jacques Carette <carette at mcmaster.ca> wrote:
> +1
> Jacques
>
> On 09/05/2011 6:49 PM, Daniel Fischer wrote:
>>
>> I would like to propose the elimination of the special error case
>>
>> gcd 0 0 = error "Prelude.gcd: gcd 0 0 is undefined"
>>
>> to replace it with
>>
>> gcd 0 0 = 0
>>
>> (which would be an automatic consequence of removing the above line).
>>
>> Rationale:
>>
>> 1. It makes gcd a total function.
>> 2. It makes gcd associative.
>> 3. It makes folding gcd over a list safe.
>> 4. It conforms to common mathematical practice:
>>
>> In a commutative ring, a greatest common divisor of two elements a, b is
>> a common divisor g of a and b such that every common divisor d of a and b
>> also divides g (if R is a commutative ring, a \in R, d \in R is a divisor
>> of a iff there exists c \in R with a = d*c [leaving out noncommutative
>> rings for simplicity]).
>> Since every ring element divides 0, the above definition entails
>> gcd 0 0 = 0.
>>
>> Further, in a principal ideal ring, the greatest common divisors of two
>> elements a and b are the generators of the ideal (a,b), again that
>> characterisation of greatest common divisors says gcd 0 0 = 0:
>> (0,0) = {0} = (0).
>>
>> Pros: see above.
>>
>> Cons: ?
>> I'm not aware of any, the change shouldn't break existing code, since that
>> would have to check for the special case anyway.
>>
>> Daniel
>>
>> _______________________________________________