People write on gcd 0 0 : Alan Bawden <Alan@LCS.MIT.EDU>
If you take the point-of-view that gcd is actually an operation on ideals, then gcd(0, 0) is 0. I.e. define gcd(x, y) to be the smallest z >= 0 such that {m*x + n*y | m, n in Z} = {n*z | n in Z}. This is probably the most natural and general definition of gcd, and is, in fact, what many mathematicians would expect.
Also, it is nice to be able to know that gcd(x, 0) = x for -all- x.
Frank Seaton Taylor <fstaylo@alpha.ncsc.mil> writes T> Let me chime in in favor of gcd(0,0) = 0 rather than undefined. T> T> On Tuesday, December 11, 2001, at 01:07 , Alan Bawden wrote: T> T> > Also, it is nice to be able to know that gcd(x, 0) = x for -all- x. T> T> Alan is in good company: T> T> 1. Steele in "Common Lisp: The Language" says the same thing. T> T> 2. Knuth in "The Art of Computer Programming" defines gcd(0,0)=0. T> classic algebra All right. Let us try to investigate this. In such cases one should consult mathematics, not programming. So, let us ignore "Common Lisp ...". And Knuth is all right, I think. Further, the definintion
gcd(x, y) to be the smallest z >= 0 such that {m*x + n*y | m, n in Z} = {n*z | n in Z}
is not natural. In particular, how does it generalize to gcd X Y for polynomials in X, Y with rational coefficients? It is 1. And how would one obtain 1 = f*X + g*Y ? According to classic algebra (Kummer, I guess), gcd x y in (such and such) domain R is the least by inclusion principal ideal (g) that includes the ideal (x, y). Here (a1..an) = set of all combinations y1*a1 + .. + yn*an, yi from R. According to this definition, gcd (X) (Y) = (1) in polynomials, all right, and gcd n m :: Integer is (0) Because (0) is the least by inclusion principal ideal containing (0). And this also contradicts the part "greatest integer that divides ..." in recent Haskell specification. Probably, the best specification would be gcd n m :: Integer = if n == 0 && m == 0 then 0 else greatest integer that divides both n and m ----------------- Serge Mechveliani mechvel@botik.ru
From: "S.D.Mechveliani" <mechvel@math.botik.ru> Date: Thu, 13 Dec 2001 12:53:32 +0300 Further, the definintion
gcd(x, y) to be the smallest z >= 0 such that {m*x + n*y | m, n in Z} = {n*z | n in Z}
is not natural. In particular, how does it generalize to gcd X Y for polynomials in X, Y with rational coefficients? Well, that -is- the way gcd is defined in the commutative algebra textbook I used in graduate school -- I just specialized the definition for the case of the ring of integers, and so I didn't mention that Z was a principle ideal domain. Polynomials in two variables aren't a PID, so yes, you'd have to restore some things I left out. When I said my definition was "general" I suppose I should have anticipated someone would generalize in a way I hadn't intended... (Actually, that definition doesn't even generalize exactly to the Gaussian Integers, where "z >= 0" would have to be replaced by some specification of a region of the complex plane.) ... Probably, the best specification would be gcd n m :: Integer = if n == 0 && m == 0 then 0 else greatest integer that divides both n and m Fortunately, we all seem to agree on what the actual definition should be. I did make a mistake in my previous message. I said that it was nice that gcd(0, x) = x for all x. I should have said: gcd(0, x) = abs(x).
participants (2)
-
Alan Bawden -
S.D.Mechveliani