Path: csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!feeder.erje.net!eu.feeder.erje.net!newsfeed.xs4all.nl!newsfeed1a.news.xs4all.nl!xs4all!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail Return-Path: X-Original-To: python-list@python.org Delivered-To: python-list@mail.python.org X-Spam-Status: OK 0.002 X-Spam-Evidence: '*H*': 1.00; '*S*': 0.00; 'value,': 0.04; 'definitions.': 0.07; 'function:': 0.09; 'received:80.91': 0.09; 'received:80.91.229': 0.09; 'received:gmane.org': 0.09; 'received:list': 0.09; 'violates': 0.09; 'wrapped': 0.09; 'python': 0.11; '(100,': 0.16; '20)': 0.16; 'b):': 0.16; 'googling': 0.16; 'integers.': 0.16; 'naming': 0.16; 'normally,': 0.16; 'received:80.91.229.3': 0.16; 'received:plane.gmane.org': 0.16; 'recipes': 0.16; 'renaming': 0.16; 'skip:> 20': 0.16; 'alpha': 0.16; 'wrote:': 0.18; 'module': 0.19; 'solution.': 0.20; 'header:User-Agent:1': 0.23; 'error': 0.23; 'mathematical': 0.24; 'tells': 0.24; 'url:02': 0.24; 'versions': 0.24; "i've": 0.25; 'mention': 0.26; 'excel': 0.26; 'somewhere': 0.26; 'defined': 0.27; 'values': 0.27; 'header:X-Complaints-To:1': 0.27; 'header :In-Reply-To:1': 0.27; 'function': 0.29; 'generally': 0.29; 'properties': 0.29; "doesn't": 0.30; '(like': 0.30; "i'm": 0.30; 'url:wiki': 0.31; "d'aprano": 0.31; 'received:132': 0.31; 'steven': 0.31; 'url:wikipedia': 0.31; 'probably': 0.32; 'extend': 0.32; 'gold': 0.33; 'maybe': 0.34; 'could': 0.34; 'equal': 0.35; 'but': 0.35; 'there': 0.35; 'acceptable': 0.36; 'false': 0.36; 'skip:> 10': 0.36; 'url:org': 0.36; 'example,': 0.37; 'to:addr :python-list': 0.38; 'fact': 0.38; 'pm,': 0.38; 'rather': 0.38; 'url:01': 0.39; 'realize': 0.39; 'sure': 0.39; 'to:addr:python.org': 0.39; 'enough': 0.39; 'received:org': 0.40; 'even': 0.60; 'greatest': 0.60; 'negative': 0.60; 'first': 0.61; 'skip:n 10': 0.64; 'debate': 0.68; 'of:': 0.68; 'obvious': 0.74; '#2:': 0.84; 'hardly': 0.84; 'irrelevant': 0.84; 'treats': 0.84; 'hand,': 0.93 X-Injected-Via-Gmane: http://gmane.org/ To: python-list@python.org From: Wolfgang Maier Subject: Re: GCD in Fractions Date: Tue, 23 Sep 2014 18:38:55 +0200 References: <54216c8e$0$29966$c3e8da3$5496439d@news.astraweb.com> Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 8bit X-Gmane-NNTP-Posting-Host: px1.ruf.uni-freiburg.de User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:31.0) Gecko/20100101 Thunderbird/31.1.1 In-Reply-To: <54216c8e$0$29966$c3e8da3$5496439d@news.astraweb.com> X-BeenThere: python-list@python.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: General discussion list for the Python programming language List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Newsgroups: comp.lang.python Message-ID: Lines: 62 NNTP-Posting-Host: 2001:888:2000:d::a6 X-Trace: 1411490314 news.xs4all.nl 2912 [2001:888:2000:d::a6]:59571 X-Complaints-To: abuse@xs4all.nl Xref: csiph.com comp.lang.python:78224 On 09/23/2014 02:50 PM, Steven D'Aprano wrote: > > Normally, gcd is only defined for non-negative integers. Wolfram Mathworld, > for example, doesn't mention negative values at all (as far as I can see): > > http://mathworld.wolfram.com/GreatestCommonDivisor.html > > although buried deep in the documentation for Mathematica's GCD function is > hidden the fact that it treats GCD(-a, -b) the same as GCD(a, b): > > http://functions.wolfram.com/IntegerFunctions/GCD/04/02/01/ > > and sure enough Wolfram Alpha tells me that the GCD of *all* of: > > (100, 20) > (-100, 20) > (100, -20) > (-100, -20) > > are equal to +20. On the other hand, Excel and LibreOffice both give an > error for the GCD of a negative value, and I've seen versions of gcd() > which do the same as fractions.gcd. So I think there is not one single > standard way to extend GCD to negative numbers. > Well, Excel and LibreOffice can hardly be considered the gold standard when it comes to mathematical definitions. I'm no mathematician either, but Wikipedia has this to say about the properties of gcd: http://en.wikipedia.org/wiki/Greatest_common_divisor#Properties fractions.gcd violates several of them, like: #2: gcd(a, 0) = |a|, for a ≠ 0, since any number is a divisor of 0, and the greatest divisor of a is |a|. >>>fractions.gcd(-7, 0) -7 #8: The gcd is a commutative function: gcd(a, b) = gcd(b, a). >>>fractions.gcd(3, -7) == fractions.gcd(-7, 3) False While at first I thought this to be a rather irrelevant debate over module private vs public naming conventions, I now think the OP is probably right and renaming fractions.gcd to fractions._gcd may be a good idea. Googling for recipes to calculate the gcd using python brings up fractions.gcd as a general answer (like at stackoverflow: http://stackoverflow.com/questions/11175131/code-for-greatest-common-divisor-in-python) and it is not obvious for non-mathematicians to realize that it is NOT a generally acceptable solution. Maybe fractions.gcd could be renamed, but be wrapped or reimplemented correctly somewhere else in the stdlib or even in fractions ? Wolfgang