Re: [Haskell-cafe] Re: gcd
Am Sonntag 03 Mai 2009 00:17:22 schrieb Achim Schneider: Steve stevech1...@yahoo.com.au wrote: It is useful to define gcd(0, 0) = 0 and lcm(0, 0) = 0 because then the natural numbers become a complete distributive lattice with gcd as meet and lcm as join operation. This extension of the definition is also compatible with the generalization for commutative rings given below. Ouch. Speak of mathematicians annoying programmers by claiming that 0 isn't divisible by any of [1..], Beg pardon? 0 is divisible by all of them. And while we're talking about rings, 0 is also divisible by 0. and further implying that 0 is bigger than all of those, 'Tis, in the divisibility preorder :) not to mention justifying all that with long words. Sorry for the long words, but having gcd 0 0 == lcm 0 0 == 0 is the sensible thing and having it differently in Haskell is a bad mistake (IMO). Damn them buggers. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: gcd
On Sat, May 2, 2009 at 4:17 PM, Achim Schneider bars...@web.de wrote: Steve stevech1...@yahoo.com.au wrote: It is useful to define gcd(0, 0) = 0 and lcm(0, 0) = 0 because then the natural numbers become a complete distributive lattice with gcd as meet and lcm as join operation. This extension of the definition is also compatible with the generalization for commutative rings given below. Ouch. Speak of mathematicians annoying programmers by claiming that 0 isn't divisible by any of [1..], and further implying that 0 is bigger than all of those, not to mention justifying all that with long words. Damn them buggers. 0 is divisible by everything. It's bigger than all of them with respect to divisibility, not size. Which you may have known. Your irony was too complex for me :-p Lukk ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: gcd
Having gcd(0,0) = 0 doesn't mean that 0 is not divisible by any other natural number. On the contrary, any natural trivially divides 0 since n*0 = 0. Perhaps the disagreement is over what is meant by greatest. The greatest in gcd is not w.r.t. the canonical ordering on the naturals; rather w.r.t. the partial order given by the divides relation. Similarly for the least in lcm. Suppose gcd(0,0) = a. Then a|0, and if b|0 then b|a. (That's what it means to be the gcd.) So what is a? Since every natural number divides zero, a must be divisible by every natural number. The only natural number with this property is 0, which can be proved using the essential uniqueness of prime factorizations and infinitude of primes. So having gcd(0,0) = 0 isn't just useful, it's the correct thing to do. I hope that didn't use too many long words. :) -Nathan Bloomfield Grad Assistant, University of Arkansas, Fayetteville On Sat, May 2, 2009 at 5:17 PM, Achim Schneider bars...@web.de wrote: Steve stevech1...@yahoo.com.au wrote: It is useful to define gcd(0, 0) = 0 and lcm(0, 0) = 0 because then the natural numbers become a complete distributive lattice with gcd as meet and lcm as join operation. This extension of the definition is also compatible with the generalization for commutative rings given below. Ouch. Speak of mathematicians annoying programmers by claiming that 0 isn't divisible by any of [1..], and further implying that 0 is bigger than all of those, not to mention justifying all that with long words. Damn them buggers. -- (c) this sig last receiving data processing entity. Inspect headers for copyright history. All rights reserved. Copying, hiring, renting, performance and/or quoting of this signature prohibited. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: gcd
Nathan Bloomfield nblo...@gmail.com wrote: The greatest in gcd is not w.r.t. the canonical ordering on the naturals; rather w.r.t. the partial order given by the divides relation. This, to defend myself, was not how it was explained in high school. -- (c) this sig last receiving data processing entity. Inspect headers for copyright history. All rights reserved. Copying, hiring, renting, performance and/or quoting of this signature prohibited. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: gcd
This, to defend myself, was not how it was explained in high school. No worries. I didn't realize this myself until college; most nonspecialist teachers just don't know any better. Nor did, it appears, the original authors of the Haskell Prelude. :) BTW, this definition of gcd makes it possible to consider gcds in rings that otherwise have no natural order- such as rings of polynomials in several variables, group rings, et cetera. Nathan Bloomfield On Sun, May 3, 2009 at 11:16 AM, Achim Schneider bars...@web.de wrote: Nathan Bloomfield nblo...@gmail.com wrote: The greatest in gcd is not w.r.t. the canonical ordering on the naturals; rather w.r.t. the partial order given by the divides relation. This, to defend myself, was not how it was explained in high school. -- (c) this sig last receiving data processing entity. Inspect headers for copyright history. All rights reserved. Copying, hiring, renting, performance and/or quoting of this signature prohibited. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: gcd
Something that perhaps could be added is that leaving 0 `gcd` 0 undefined has two obvious annoying consequences: gcd is no longer idempotent (i.e. we don't have a `gcd` a = a, for all a), and it is no longer associative ((a `gcd` 0) `gcd` 0 is well-defined whilst a `gcd` (0 `gcd` 0) is not). (We actually wrote something about this on a recent paper. If you're interested, see http://www.joaoff.com/publications/2009/euclid-alg ) Regards, Joao 2009/5/3 Nathan Bloomfield nblo...@gmail.com This, to defend myself, was not how it was explained in high school. No worries. I didn't realize this myself until college; most nonspecialist teachers just don't know any better. Nor did, it appears, the original authors of the Haskell Prelude. :) BTW, this definition of gcd makes it possible to consider gcds in rings that otherwise have no natural order- such as rings of polynomials in several variables, group rings, et cetera. Nathan Bloomfield On Sun, May 3, 2009 at 11:16 AM, Achim Schneider bars...@web.de wrote: Nathan Bloomfield nblo...@gmail.com wrote: The greatest in gcd is not w.r.t. the canonical ordering on the naturals; rather w.r.t. the partial order given by the divides relation. This, to defend myself, was not how it was explained in high school. -- (c) this sig last receiving data processing entity. Inspect headers for copyright history. All rights reserved. Copying, hiring, renting, performance and/or quoting of this signature prohibited. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: gcd
Am Sonntag 03 Mai 2009 18:16:38 schrieb Achim Schneider: Nathan Bloomfield nblo...@gmail.com wrote: The greatest in gcd is not w.r.t. the canonical ordering on the naturals; rather w.r.t. the partial order given by the divides relation. Nitpick: it's not a partial order, but a preorder (2 | (-2), (-2) | 2, 2 /= (-2)). This, to defend myself, was not how it was explained in high school. Understandably. One wouldn't want to confuse the average pupil with too abstract concepts like arbitrary rings or preorders. Unfortunately that leads to teaching concepts of primes, greatest common divisors and least common multiples which don't agree with the modern mathematical concepts :-( ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: gcd
Steve stevech1...@yahoo.com.au wrote: It is useful to define gcd(0, 0) = 0 and lcm(0, 0) = 0 because then the natural numbers become a complete distributive lattice with gcd as meet and lcm as join operation. This extension of the definition is also compatible with the generalization for commutative rings given below. Ouch. Speak of mathematicians annoying programmers by claiming that 0 isn't divisible by any of [1..], and further implying that 0 is bigger than all of those, not to mention justifying all that with long words. Damn them buggers. -- (c) this sig last receiving data processing entity. Inspect headers for copyright history. All rights reserved. Copying, hiring, renting, performance and/or quoting of this signature prohibited. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
