| 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 Well, thank you all those that have contributed. My original point was simply to say greatest (positive) integer that divides both n and m but debate seems to have swirled round whether (gcd 0 0) should be 0 or an error. Currently in H98 it's an error; but it is the kind of thing I'm willing to change IF there is a consensus, because it will only make more programs work. Is there a consensus that such a change would be desirable? If someone could write a sentence or two to explain why gcd 0 0 = 0, (ideally, brief ones I can put in the report by way of explanation), I think that might help those of us who have not followed the details of the discussion. Simon
Simon Peyton Jones (simonpj@microsoft.com) wrote: : If someone could write a sentence or two to explain why gcd 0 0 = 0, : (ideally, brief ones I can put in the report by way of explanation), : I think that might help those of us who have not followed the details : of the discussion. Division in the context of gcds (of integers) is usually defined along the lines of: An integer $a$ divides integer $b$ if there exists an integer $c$ such that $a c= b$. Note that here division is a *relation* an not a *function*/*operator*. Given the definition of division being a relation it makes perfect sense to say that $0$ divides $0$ which is why gcd 0 0 = 0; and gcd 0 0 /= error "Blah" The gcd of two integers is usually defined as a non-negative number to make it unique. HTH. PS: I am strongly in favour of gcd 0 0 = 0. Regards, Marc van Dongen
Marc van Dongen (dongen@cs.ucc.ie) wrote: : An integer $a$ divides integer $b$ if there exists an integer : $c$ such that $a c= b$. [snip] : gcd 0 0 = 0; and : gcd 0 0 /= error "Blah" To make clear why $0$ (and not any other non-zero integer) is the gcd of $0$ and $0$ I should have added that for the integer case $g$ is called a greatest common divisor (gcd) of $a$ and $b$ if it satifies each of the following two properties: 1) $g$ divides both $a$ and $b$; 2) if $g'$ is a common divisor of $a$ and $b$ then $g'$ divides $g$. First notice that $0$ is a gcd of $0$ and $0$ because of the following: *) $0$ divides $0$ (and divides $0$); *) whenever $g'$ is an integer that divides $0$ and divides $0$ then $g'$ divides $0$. Next notice that if $g$ is any non-zero integer then $g$ cannot be a gcd of $0$ and $0$ because $0$ (a common divisor of $0$ and $0$) does not divide $g$. Finally, observe that this makes $0$ the unique gcd of $0$ and $0$. : The gcd of two integers is usually defined as a non-negative : number to make it unique. Regards, Marc van Dongen
From: Marc van Dongen <dongen@cs.ucc.ie> Date: Sun, 16 Dec 2001 13:35:59 +0000
Marc van Dongen (dongen@cs.ucc.ie) wrote:
: An integer $a$ divides integer $b$ if there exists an integer : $c$ such that $a c= b$.
To make clear why $0$ (and not any other non-zero integer) is the gcd of $0$ and $0$ I should have added that for the integer case $g$ is called a greatest common divisor (gcd) of $a$ and $b$ if it satifies each of the following two properties:
1) $g$ divides both $a$ and $b$; 2) if $g'$ is a common divisor of $a$ and $b$ then $g'$ divides $g$.
In case it isn't clear already, these definitions make a lattice on the positive integers, with divides ~ leq, gcd ~ meet and lcm ~ join, using the report's definitions of gcd and lcm. (Choosing the positive result for gcd/lcm is equivalent to noting that divides is a partial preorder on the non-zero integers, and that the quotient identifies x and -x). The only thing that is lacking to make it a lattice on the non-negative integers, is that gcd 0 0 = 0 . All other cases involving zero (i.e., gcd 0 x = x for non-zero x, and lcm 0 x = 0 for all x) are consistent with 0 being the maximal element in the lattice, i.e., that all integers divide zero. Lars Mathiesen (U of Copenhagen CS Dep) <thorinn@diku.dk> (Humour NOT marked)
From: Lars Henrik Mathiesen <thorinn@diku.dk> Date: 17 Dec 2001 14:50:21 -0000 ... In case it isn't clear already, these definitions make a lattice on the positive integers, with divides ~ leq, gcd ~ meet and lcm ~ join, using the report's definitions of gcd and lcm. Indeed, that's a nice way of putting it. How about if the report just says: In order to make the non-negative integers into a lattice under `gcd' and `lcm', we define `gcd 0 0 = 0'.
Alan Bawden (Alan@LCS.MIT.EDU) wrote: : In case it isn't clear already, these definitions make a lattice on : the positive integers, with divides ~ leq, gcd ~ meet and lcm ~ join, : using the report's definitions of gcd and lcm. : : Indeed, that's a nice way of putting it. How about if the report just : says: : : In order to make the non-negative integers into a lattice under `gcd' : and `lcm', we define `gcd 0 0 = 0'. It would surely make things a lot less accessible to people (including me) who do not have any (or limited) knowledge about lattices. Why not make it more accessible and use the following rule (ore something similar)? The greates common divison (gcd) of two integers a and b is the unique non-negative integer g which has each of the following two properties: 1) g divides both a and b; and 2) if g' also divides both a and b then g' also divides g, Here an integer a divides an integer b if there is an integer c such that b = c*a. Note that if you regard an integer a to be greater than another integer b if b divides a then the gcd of two intgerers may also be regarded as the greatest common divisor of a and b. Regards, Marc van Dongen
From: Marc van Dongen <dongen@cs.ucc.ie> Date: Tue, 18 Dec 2001 09:32:49 +0000
Alan Bawden (Alan@LCS.MIT.EDU) wrote: : Indeed, that's a nice way of putting it. How about if the report just : says: : : In order to make the non-negative integers into a lattice under `gcd' : and `lcm', we define `gcd 0 0 = 0'.
It would surely make things a lot less accessible to people (including me) who do not have any (or limited) knowledge about lattices. Why not make it more accessible and use the following rule (ore something similar)?
The greates common divison (gcd) of two integers a and b is the unique non-negative integer g which has each of the following two properties: 1) g divides both a and b; and 2) if g' also divides both a and b then g' also divides g, Here an integer a divides an integer b if there is an integer c such that b = c*a.
This is exactly what you get if you plug the relation 'divides' on the non-negative integers into the definition of meet in a lattice. So this formulation is no more or less complex to use than the lattice one --- and people who do know about lattices will probably realize this pretty fast. It all depends on who you want to convince that gcd 0 0 should be 0, the mathematicians (by elegance) or the programmers (by concreteness). But since it seems that Simon is just going to put 'it is so' in the report, the point is moot. Lars Mathiesen (U of Copenhagen CS Dep) <thorinn@diku.dk> (Humour NOT marked)
Lars Henrik Mathiesen (thorinn@diku.dk) wrote: : > Alan Bawden (Alan@LCS.MIT.EDU) wrote: : > : Indeed, that's a nice way of putting it. How about if the report just : > : says: : > : : > : In order to make the non-negative integers into a lattice under `gcd' : > : and `lcm', we define `gcd 0 0 = 0'. [snip] : This is exactly what you get if you plug the relation 'divides' on the : non-negative integers into the definition of meet in a lattice. So : this formulation is no more or less complex to use than the lattice : one --- and people who do know about lattices will probably realize : this pretty fast. I disagree. Alan is talking about adding things to the haskell report. That document should be accessible to as many people as possible. I have not yet met anybody who had lattice theory in primary and/or secondary school. On the other hand I *have* met quite a few of them who have a pretty good idea about what it means for one number to divide another. [snip] Regards, Marc van Dongen -- Marc van Dongen | dongen@cs.ucc.ie | Computer Science Department | Western Road | () ASCII ribbon campaign University College Cork | Cork, Ireland | /\ against HTML mail phone: +353 (0)21 4903578 | fax: 4903113 |
From: "Simon Peyton-Jones" <simonpj@microsoft.com> Date: Fri, 14 Dec 2001 01:18:56 -0800 ... If someone could write a sentence or two to explain why gcd 0 0 = 0, (ideally, brief ones I can put in the report by way of explanation), I think that might help those of us who have not followed the details of the discussion. Well, Serge and I have both offered variations on the real reason why mathematicians agree that gcd 0 0 = 0. I prefer my simpler specialized-for-integers version, but I suspect even that is more mathematics than you want. At the other extreme, you could follow Knuth and simply state: "it is convenient to set gcd(0, 0) = 0", but that seems a bit unconvincing. If I were in your shoes, I'd simply pass the buck to the authorities by saying something like: "Mathematicians agree that gcd(0, 0) = 0". Incidentally, somebody wrote here that Common Lisp defines `(gcd 0 0)' to be 0, but it looks to me like all the language definition really does is state that `(gcd)' (no arguments) is 0 because 0 "is an identity for this operation" (which is technically false, but never mind), from which it is natural for the reader to conclude that `(gcd 0 0)' must be 0.
participants (4)
-
Alan Bawden -
Lars Henrik Mathiesen -
Marc van Dongen -
Simon Peyton-Jones