If everyone likes this I'll put it in; otherwise I'll simply state that gcd 0 0 is defined to be 0. Christoph does not like this, but the weight of world opinion seems to be fairly clearly in favour of gcd 0 0 = 0. Let's try to wrap this one up. Simon | -----Original Message----- | From: Alan Bawden [mailto:Alan@LCS.MIT.EDU] | Sent: 17 December 2001 18:45 | To: haskell@haskell.org; Simon Peyton-Jones | Subject: Re: gcd 0 0 = 0 | | | 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'. |
"Simon" == Simon Peyton-Jones <simonpj@microsoft.com> writes:
Simon> Christoph does not like this It's OK if the definition is clear; it wasn't using the words "positive" or "greatest integer". Stating "gcd 0 0 = 0" explicitly is a good thing, even if it could be expressed verbatim; people may think about the mathematical background, but they should not need to think about the meaning of the definition. Anyway, I'm still against promoting 1 to a prime number :-) Cheers -- Christoph
"Simon" == Simon Peyton-Jones <simonpj@microsoft.com> writes:
Simon> Christoph does not like this
I still don't like this. 0 has never, and will never, divide anything, in particular not 0. 0 may be a prime factor of 0 (see also below!), but that is different. It is not the greatest (in the ordinary sense) divisor of 0. Indeed, +infinity is a much larger divisor of 0... I'm not in favour of using a very special-purpose order, not used for anything else, and that isn't even an order but a preorder, just to motivate gcd 0 0 = 0. Even if using this very special-purpose preorder, an infinity would be included in the 'top' equivalence class, and if we pick a representative value on the basis of which is 'greater' in the ordinary sense for integers augmented with infinities(!), then +infinity should be the representative value. Thus, in any case, gcd 0 0 = +infinity. This is easy enough for Integer, where +infinity and -infinity can easily be made representable (and should be made representable), but harder for a 'pure hardware' Int datatype. But in an ideal world, gcd 0 0 = +infinity with no error or exception.
It's OK if the definition is clear; it wasn't using the words "positive" or "greatest integer".
Stating "gcd 0 0 = 0" explicitly is a good thing, even if it could be expressed verbatim; people may think about the mathematical background, but they should not need to think about the meaning of the definition.
Anyway, I'm still against promoting 1 to a prime number :-)
Why? If EVERY natural number is to have a prime factorisation, then BOTH 0 AND 1 have to be promoted to prime numbers; otherwise 1 and 0 cannot be prime factorised; in addition to that 1 is then a prime factor of any number (that can be excluded from the *minimal* list of prime factors except for 1)... There is no fundamental reason to except 1 from being a prime number. But there is a fundamental reason to say that 0 can never be a divisor (i.e. 0|0 is false; x|y is true iff x is a *non-zero* factor of y; the 'non-zero' part is often left implicit (e.g. one is only talking about strictly positive integers), which is part of the reason why we are having this discussion). If you want something similar to gcd, but that returns 0 for 0 and 0, then it is the 'product of all common prime factors'; where 1 has the (non-minimal) prime factorisation [1, 1, ...], 0 has the (non-minimal) prime factorisation [0, 1, 2, ...], and 1 is included at least once in the (non-minimal) prime factorisation of any natural number. If you want a parallel to the divides relation where 0 and 0 are related: 0 is a factor of 0. A prime number is a number that has no integer *between* 1 and itself as factors. People often say "except" instead of "between", but that does not work for 0, nor for the non-minimal prime factorisations that people seem to be interested in, given the interest in having gcd 0 0 = 0 (which isn't the gc*d*!). Again, the context is often strictly positive integers, and 'between' and 'except' are then equivalent. For no apparent reason 1 is usually also excepted, but that does not work for the prime factorisation of 1, nor for finding the product of all common prime factors of 1 and another natural number... For integers, -1 is also a prime number, and for imaginary integers, i is also a prime number... I'm sure somebody can give a nice definition of a partial order (not just preorder) lattice with 1 as the min value and 0 as the max value (just larger than the infinities), if you absolutely want a lattice with a gcd-*like* meet and lcm-*like* join for this (the, positive bias, factor-of order). I'd be happy to support such gcd-*like* (pcf?) and lcm-*like* functions, but they aren't the gcd, nor the lcm (e.g. pcf (-1) (-1) = -1, not 1, etc.). If you don't like adding these, then I suggest leaving things completely as they are. Squeezing in two operations into one just because they have the same results over the first quadrant is not something I find to be too good. Odd one out? /kent k
On Tue, Dec 18, 2001 at 06:00:30PM +0100, Kent Karlsson wrote:
Why? If EVERY natural number is to have a prime factorisation, then BOTH 0 AND 1 have to be promoted to prime numbers;
1 has a perfectly fine prime factorization. It is the product of 0 primes, the null product. (A null product is defined, for very good reasons, to be 1, just like a null sum is defined to be 0.) I could see defences of calling 0 a prime, although it is not standard mathematical practice. The ideal generated by 0 is a prime ideal, for one thing. 0 would still not have a unique prime factorization, however. (But Haskell should not unilaterally decide to violate standard mathematical terminology!)
... But there is a fundamental reason to say that 0 can never be a divisor (i.e. 0|0 is false; x|y is true iff x is a *non-zero* factor of y; the 'non-zero' part is often left implicit (e.g. one is only talking about strictly positive integers), which is part of the reason why we are having this discussion).
What fundamental reason do you have in mind? Why do you use this definition of divisibility? (I'm curious; other mathematicians give the same definition, and I can't see why.) This thread made me curious, so I did a little library research. I was surprised to discover that mathematicians discover on this, the domain of definition of "gcd a b": Domain References ------ ---------- a /= 0, b /= 0 Lang, "Algebra, 3rd Edition" Hasse, "Number Theory" a, b not both 0 Koblitz, "A Course on Number Theory and Cryptography" all a, b allowed MacLane and Birkhoff, "Algebra, 2nd Edition" Koch, "Number Theory" At least the books by Lang and MacLane-Birkhoff are standard references. Note that the definitions all agree when they are defined (with gcd 0 0 = 0). As I said, I was surprised; to me, the definiton with all a and b is the more natural one. I still recommend using the full domain (especially since exceptions are awkward to deal with in Haskell), but I'm not as certain. Best, Dylan Thurston
The general meaning of `having a prime factorization' is that every non-zero element is uniquely a product of a unit and a product of primes. The algebraic structures where unique factorizations live are `unique factorization domains' (UFDs) of which a central class is formed by the ring of polynomials over a field. Here the non-zero elements of the field are the units; no one has ever suggested calling them primes! In a general UFD one can only speak of _a_ gcd of two elements x and y, meaning an element d such that one has (x, y) = (d), an equality of ideals. In some special cases, there is a natural choice for d (e.g., in the integers, the non-negative d; in the ring of polynomials over a field, the monic d (having leading coeff. 1)). In some UFDs there is no canonical choice (e.g. in the Gaussian integers, a + ib for a, b integers). gcd(0, 0) = 0. Cheers, Michael Ackerman Dylan Thurston wrote:
On Tue, Dec 18, 2001 at 06:00:30PM +0100, Kent Karlsson wrote:
Why? If EVERY natural number is to have a prime factorisation, then BOTH 0 AND 1 have to be promoted to prime numbers;
1 has a perfectly fine prime factorization. It is the product of 0 primes, the null product. (A null product is defined, for very good reasons, to be 1, just like a null sum is defined to be 0.)
I could see defences of calling 0 a prime, although it is not standard mathematical practice. The ideal generated by 0 is a prime ideal, for one thing. 0 would still not have a unique prime factorization, however. (But Haskell should not unilaterally decide to violate standard mathematical terminology!)
... But there is a fundamental reason to say that 0 can never be a divisor (i.e. 0|0 is false; x|y is true iff x is a *non-zero* factor of y; the 'non-zero' part is often left implicit (e.g. one is only talking about strictly positive integers), which is part of the reason why we are having this discussion).
What fundamental reason do you have in mind? Why do you use this definition of divisibility? (I'm curious; other mathematicians give the same definition, and I can't see why.)
This thread made me curious, so I did a little library research. I was surprised to discover that mathematicians discover on this, the domain of definition of "gcd a b":
Domain References ------ ---------- a /= 0, b /= 0 Lang, "Algebra, 3rd Edition" Hasse, "Number Theory"
a, b not both 0 Koblitz, "A Course on Number Theory and Cryptography"
all a, b allowed MacLane and Birkhoff, "Algebra, 2nd Edition" Koch, "Number Theory"
At least the books by Lang and MacLane-Birkhoff are standard references. Note that the definitions all agree when they are defined (with gcd 0 0 = 0).
As I said, I was surprised; to me, the definiton with all a and b is the more natural one. I still recommend using the full domain (especially since exceptions are awkward to deal with in Haskell), but I'm not as certain.
Best, Dylan Thurston
_______________________________________________ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
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
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
participants (6)
-
Ch. A. Herrmann -
Dylan Thurston -
Jan de Wit -
Kent Karlsson -
Michael Ackerman -
Simon Peyton-Jones