gcd 0 0 = 0

Kent Karlsson kentk@md.chalmers.se
Wed, 19 Dec 2001 14:04:25 +0100


Let me try again:

	greatest -> maximum/supremum of a set of integers (plain everyday order)

	common -> intersection (plain everyday intersection of sets)

	divisor (of an integer value v) ->
		an integer value m, such that v/m is defined and, if so, is an integer

	factor (of an integer value v) ->
		an integer value m, such that there is an integer value n such that m*n=v

So (mock Haskell syntax; set expression really):

	greatest_common_divisor a b = max (intersection {all divisors of a} {all divisors of b})


What is the supremum (result of max in the expression above) if a and b are both 0?
(You're allowed to use values not prescribed by Haskell to exist. ;-)

(You can replace "divisors" by "factors" in that expression and still get the same result.)

I may agree that an operation *similar* to gcd, where <0,0> as argument
returns 0 is useful (maybe even more useful than gcd!).  But that operation
is still not the gcd (and might even return other results thaN gcd also for
other value pairs than <0,0>; in particlar negatives; depending on what is
found most useful).

If you want to replace gcd by some other, similar, operation, please go ahead.
But call it something else, because it is something else. If you want to generalise
that to polynomials or Gaussian integers (or at least imaginary integers, as opposed
to complex integers), fine (though not for the current standard Haskell library).
(Micheal, I am interested in the Guassian integer variety of this. If you like,
you can expand on what you said in an off-list message, or give me a reference.)

		Kind (and somewhat fundamentalist) regards
		/kent k


> -----Original Message-----
> From: haskell-admin@haskell.org [mailto:haskell-admin@haskell.org]On
> Behalf Of Jan de Wit
> Sent: den 19 december 2001 01:15
> To: haskell@haskell.org
> Subject: Re: gcd 0 0 = 0
> 
> 
> Why not define gcd a b as the largest (in 'normal' order) 
> integer d such
> that the set of sums of
> multiples of a and b {na+mb | n <- Z, m <- Z} is equal to the set of
> multiples of d
> {nd | n <- Z}? Easy to understand, no talk of division, 
> lattices, rings,
> ideals etcetera, and it covers the cases with 0.
> 
> Cheers, Jan de Wit
> 
> 
> 
> _______________________________________________
> Haskell mailing list
> Haskell@haskell.org
> http://www.haskell.org/mailman/listinfo/haskell