People write on gcd 0 0 : Alan Bawden <[EMAIL PROTECTED]>
> 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 <[EMAIL PROTECTED]> 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 [EMAIL PROTECTED] _______________________________________________ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell