Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.python > #78314
| Path | csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!news.mixmin.net!aioe.org!.POSTED!not-for-mail |
|---|---|
| From | "Robert E. Beaudoin" <rbeaudoin@comcast.net> |
| Newsgroups | comp.lang.python |
| Subject | Re: GCD in Fractions |
| Date | Wed, 24 Sep 2014 19:19:36 -0400 |
| Organization | Aioe.org NNTP Server |
| Lines | 63 |
| Message-ID | <lvvji8$cfc$1@speranza.aioe.org> (permalink) |
| References | <pfGdnaNKbb7-sbzJnZ2dnUVZ8vudnZ2d@brightview.co.uk> <54216c8e$0$29966$c3e8da3$5496439d@news.astraweb.com> <lvs7lq$vrn$1@ger.gmane.org> <mailman.14277.1411493200.18130.python-list@python.org> <CYmdneCJKbm7LLzJnZ2dnUVZ7vadnZ2d@brightview.co.uk> <mailman.14280.1411494972.18130.python-list@python.org> <tfidne0ioO6jdbzJnZ2dnUVZ7rednZ2d@brightview.co.uk> <5422ae8b$0$29980$c3e8da3$5496439d@news.astraweb.com> <WdGdnY7uu9nKW7_JnZ2dnUVZ7omdnZ2d@brightview.co.uk> |
| NNTP-Posting-Host | p225Y0WoDt/W4qaiwOEwMw.user.speranza.aioe.org |
| Mime-Version | 1.0 |
| Content-Type | text/plain; charset=ISO-8859-1; format=flowed |
| Content-Transfer-Encoding | 7bit |
| X-Complaints-To | abuse@aioe.org |
| User-Agent | Mozilla/5.0 (X11; Linux x86_64; rv:24.0) Gecko/20100101 Thunderbird/24.7.0 |
| X-Notice | Filtered by postfilter v. 0.8.2 |
| Xref | csiph.com comp.lang.python:78314 |
Show key headers only | View raw
On 09/24/14 09:25, blindanagram wrote: > On 24/09/2014 12:44, Steven D'Aprano wrote: > >> blindanagram wrote: > [snip] >> - Mathworld says that GCD of two negative numbers is a negative number; >> >> - but Mathematica says that GCD of two negative numbers is a positive; >> >> - Wikipedia agrees with Mathematica and disagrees with Mathworld; > > After looking at these (and several other) on-line mathematical sites, I > realised that I would have to go back to long standing mathemmatical > references to find how the gcd is defined by those that explicitly cover > the greatest common divisor for negative integers (I did this before > raising the issue here). > > All four that I have so far looked at have definitions that lead to > gcd(a, b) for integers being equal to gcd(|a|, |b|). I hope to visit a > University library shortly to review more. Does anyone know of such a > reference that uses a definition that conflicts with gcd(a, b) for > integers being equal to gcd(|a|, |b|)? > I doubt you'll find an advanced mathematical text that has such a definition. I think most abstract algebra texts would give a definition equivalent to saying that for any integers n and m the ideal generated by n and m is equal to the principal ideal generated by gcd(n,m); that is the heart of the matter mathematically, and this definition generalizes to other so-called "principal ideal domains" than the integers. (Don't want to Google for "ideal" and "principal ideal"? OK: an ideal is a subset of the integers closed under addition of any two of its elements, and under multiplication of any of its elements by any integer; a set of integers generates an ideal if that ideal is the intersection of all ideals containing that set, and a principal ideal is an ideal generated by a singleton set. For more elaboration, though, I'm going to point you at the internet, or better, some of those advanced texts in the library.) After working through what the definitions of ideals and principal ideals imply for the the definition above of gcd, you get the statement that k is the (or, better, a) gcd of n and m if and only if k divides n and m, and any other integer that divides both n and m divides k. The upshot is that, mathematically, gcd is only defined up to a change of sign, which helps explain why references may disagree with each other. Some authors may impose the restriction than gcd(n,m) >= 0 for all n and m (which does have the advantage that then "greatest" really means greatest and not just "greatest absolute value"), but that isn't really a necessary part of the definition as far as the mathematically important properties of gcd are concerned. All that the abstract algebra requires is that |gcd(n,m)| = |gcd(|n|,|m|)|. So implementations of gcd that sometimes return a negative value are not, it seems to me, mathematically broken, though they might violate the principle of least surprise. for-whatever-it's-worth'ly-yrs, R. Beaudoin
Back to comp.lang.python | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
GCD in Fractions blindanagram <noone@nowhere.net> - 2014-09-23 09:16 +0100
Re: GCD in Fractions Wolfgang Maier <wolfgang.maier@biologie.uni-freiburg.de> - 2014-09-23 13:53 +0200
Re: GCD in Fractions blindanagram <noone@nowhere.net> - 2014-09-23 13:48 +0100
Re: GCD in Fractions Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2014-09-23 22:50 +1000
Re: GCD in Fractions blindanagram <noone@nowhere.net> - 2014-09-23 15:37 +0100
Re: GCD in Fractions Chris Angelico <rosuav@gmail.com> - 2014-09-24 00:42 +1000
Re: GCD in Fractions Wolfgang Maier <wolfgang.maier@biologie.uni-freiburg.de> - 2014-09-23 18:38 +0200
Re: GCD in Fractions Ian Kelly <ian.g.kelly@gmail.com> - 2014-09-23 11:20 -0600
Re: GCD in Fractions blindanagram <noone@nowhere.net> - 2014-09-23 18:31 +0100
Re: GCD in Fractions Stefan Behnel <stefan_ml@behnel.de> - 2014-09-23 19:26 +0200
Re: GCD in Fractions blindanagram <noone@nowhere.net> - 2014-09-23 18:43 +0100
Re: GCD in Fractions Stefan Behnel <stefan_ml@behnel.de> - 2014-09-23 19:55 +0200
Re: GCD in Fractions blindanagram <noone@nowhere.net> - 2014-09-23 22:38 +0100
Re: GCD in Fractions Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2014-09-24 21:44 +1000
Re: GCD in Fractions blindanagram <noone@nowhere.net> - 2014-09-24 14:25 +0100
Re: GCD in Fractions Stefan Behnel <stefan_ml@behnel.de> - 2014-09-24 18:13 +0200
Re: GCD in Fractions blindanagram <noone@nowhere.net> - 2014-09-24 18:05 +0100
Re: GCD in Fractions "Robert E. Beaudoin" <rbeaudoin@comcast.net> - 2014-09-24 19:19 -0400
Re: GCD in Fractions Ian Kelly <ian.g.kelly@gmail.com> - 2014-09-24 08:26 -0600
Re: GCD in Fractions random832@fastmail.us - 2014-09-24 12:49 -0400
Re: GCD in Fractions Terry Reedy <tjreedy@udel.edu> - 2014-09-24 13:42 -0400
Re: GCD in Fractions Johann Hibschman <jhibschman@gmail.com> - 2014-09-24 14:09 -0400
Re: GCD in Fractions Mark Lawrence <breamoreboy@yahoo.co.uk> - 2014-09-23 20:30 +0100
Re: GCD in Fractions blindanagram <noone@nowhere.net> - 2014-09-23 22:48 +0100
Re: GCD in Fractions Mark Lawrence <breamoreboy@yahoo.co.uk> - 2014-09-23 23:52 +0100
Re: GCD in Fractions Mark Lawrence <breamoreboy@yahoo.co.uk> - 2014-09-24 11:42 +0100
Re: GCD in Fractions Mark Dickinson <mdickinson@enthought.com> - 2014-09-24 11:14 +0000
Re: GCD in Fractions Mark Lawrence <breamoreboy@yahoo.co.uk> - 2014-09-24 17:34 +0100
Re: GCD in Fractions blindanagram <noone@nowhere.net> - 2014-09-24 18:31 +0100
Re: GCD in Fractions Akira Li <4kir4.1i@gmail.com> - 2014-09-25 14:56 +0400
Re: GCD in Fractions Chris Angelico <rosuav@gmail.com> - 2014-09-25 21:03 +1000
Re: GCD in Fractions Ian Kelly <ian.g.kelly@gmail.com> - 2014-09-23 11:39 -0600
Re: GCD in Fractions Ian Kelly <ian.g.kelly@gmail.com> - 2014-09-23 11:40 -0600
Re: GCD in Fractions Stefan Behnel <stefan_ml@behnel.de> - 2014-09-23 20:09 +0200
Re: GCD in Fractions Terry Reedy <tjreedy@udel.edu> - 2014-09-23 15:31 -0400
csiph-web