[If this whole 'gcd' discussion is getting 'too mathematical' for this list,
I propose to continue it by private e-mail with members of the Haskell
committee. If so, please give me an e-mail address to contact.]
At 09:16 6-11-96 +0300, you wrote in reply to my 'Why not make "gcd 0 0 = 0"?':
>Hello,
>
>there was recently a letter on the subject like
> " gcd(0,0) should be 0 ".
>Unfortunately, I had lost it and cannot citate.
>
>Here are simple considerations to prevent the confusion.
>
>(1)
>gcd(0,0) = 0 is all right.
>
>But setting this would hardly improve anything. For in mathematics,
>they write gcd(a,b) (think, say, of a/gcd(a,b) )
>only after the case a=b=0 is considered separately or excluded
>by default.
But defining gcd(0,0)=0 is precisely what is needed, at least in your
example. a/gcd(a,b) is not meaningful if gcd(a,b)=0, which is equivalent
(by this definition) to a=b=0. Thus the case separation on a=b=0 follows
from gcd(a,b) being a denominator, not from a and b being zero as such.
>In other words, this would be is like setting 0/0 = 0.
I don't see the analogy at all. Could you explain it? I mean, I have not
yet seen a natural definition of division that extends naturally to the case
0/0. Which is exactly what I propose for gcd(0,0).
>(2)
>The letter contained some discource on the subject.
>Everything on gcd was explained by the classics:
>
>" gcd(a,b) is the greatest by inclusion ideal (d) among the
> ones with the property of
> (d) = {x*d | x <- R} to be contained inside
> (a)+(b) = {x*a + y*b | x,y <- R}
>"
>This was formutated so in order to fit not only the Integers.
I assume here R stands for the set of integers. A kind reader of sci.math
e-mailed me with an explanation of this definition, which I wasn't aware of.
It is the most elegant definition of 'gcd' I have seen. Let me quote his
explanation here:
>I believe the most elegant definition of the gcd and lcm is the
>following: if S is a set of integers, consider the subgroup of Z
>generated by S, that is, the set of all sums or differences of
>a finite number of elements of S. Now any subgroup of Z can be
>written in a unique way as
> mZ={mx:x@Z}(m>=0)
>so define the gcd of S to be the unique such m.
[snipped definition of lcm]
>This definition generalizes to Q and R. The difference is that
>a subgroup of Q or R is not necessarily of the above form. The
>gcd of an infinite set of rationals is not always defined (the
>lcm always is). The gcd of even a finite set of reals ({1,pi}
>for example) is not always defined.
Thus, according to this generally accepted definition, the gcd of {a,b} is
always defined for a,b in Q, and the above definition implies that gcd(0,0)
= 0. So again I propose to define "gcd 0 0 = 0", and generalize the
definition to rationals, in the Haskell Prelude.
Note that the gcd of rationals can be computed using exactly the same
algorithm that is currently used for the gcd of integers. Therefore my
proposal costs almost nothing, gaining a little generality.
>Now (1) follows trivially from this definition as well as
>
>(3)
>(the author mentions the case of the rational numbers)
>
>Here we keep in mind that for the Rationals and "the like domains",
>gcd is trivial:
> if a /= 0 then gcd(a,b) = 1.
Not so. gcd(4/3, 10/3) = 2/3, according to your own definition.
>Sergey Mechveliani
>
>[EMAIL PROTECTED]
Groetjes,
<><
Marnix
--
Marnix Klooster
[EMAIL PROTECTED]
