Path: csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!feeder.erje.net!eu.feeder.erje.net!xlned.com!feeder7.xlned.com!newsfeed.xs4all.nl!newsfeed4.news.xs4all.nl!xs4all!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.003 X-Spam-Evidence: '*H*': 0.99; '*S*': 0.00; 'operator': 0.03; 'algorithm': 0.04; 'mathematics': 0.05; 'extends': 0.09; 'imply': 0.09; 'integers': 0.09; 'integral': 0.09; 'modulo': 0.09; 'negative.': 0.09; '(second': 0.16; '24,': 0.16; 'collins': 0.16; 'domains.': 0.16; 'equation': 0.16; 'finite': 0.16; 'integers.': 0.16; 'mathematics.': 0.16; 'negative,': 0.16; 'operation,': 0.16; 'wrote:': 0.18; 'wed,': 0.18; 'input': 0.22; 'example': 0.22; 'integer': 0.24; 'specifies': 0.24; 'regardless': 0.24; 'header :In-Reply-To:1': 0.27; 'am,': 0.29; "doesn't": 0.30; 'sets': 0.30; 'message-id:@mail.gmail.com': 0.30; 'that.': 0.31; "d'aprano": 0.31; 'factor': 0.31; 'sep': 0.31; 'steven': 0.31; 'values.': 0.31; 'entirely': 0.33; 'sense': 0.34; 'could': 0.34; 'common': 0.35; 'anybody': 0.35; 'computing': 0.35; 'definition': 0.35; 'received:google.com': 0.35; 'there': 0.35; 'possible': 0.36; 'should': 0.36; 'example,': 0.37; 'positive': 0.37; 'two': 0.37; 'clear': 0.37; 'step': 0.37; 'implement': 0.38; 'depends': 0.38; 'to:addr:python-list': 0.38; 'issue': 0.38; '12,': 0.39; 'highest': 0.39; 'itself': 0.39; 'sure': 0.39; 'to:addr:python.org': 0.39; 'either': 0.39; 'greatest': 0.60; 'negative': 0.60; 'solve': 0.60; 'matter': 0.61; 'url:index': 0.63; 'such': 0.63; 'more': 0.64; 'choose.': 0.84; 'results,': 0.84; 'edition,': 0.91 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :content-type; bh=Szd5Rwfddfjv7b3bwiTZ+8dGl0JRUUmvLjaLkYc7VWE=; b=iLdorePwtDH9ID9jkOCWEDozDnWNpet+4cRYwtjDvUDbgd4tGPxR8LfVbwWTVFWRfs Af/+oi6DHdonswiZPCHeMjmiXoaXt2WX2DQkTIp+0aQJuhxnYHrWzyrvGhH8Jht3mvEr VpXuRyP5I2hZ7EfHl2TXQ0jjhfzzH+XQjU4vpgNzuSYErbRBuGrfeOHZjcGkXwt2+q5p MADcK16MLfVdtZ6cy2wXlryAyGSS1nCbSox9LAVz3Jy7QoNmD6lcx4b7nI7A6n83JtSo fl41Mrr/18a3gqYVzy6lIUTITAmAsuCwjKrc4YtzvObFtIsN7Mjb0HCLLxiqXBfP2IWo whUQ== X-Received: by 10.68.135.70 with SMTP id pq6mr9973077pbb.10.1411568846575; Wed, 24 Sep 2014 07:27:26 -0700 (PDT) MIME-Version: 1.0 In-Reply-To: <5422ae8b$0$29980$c3e8da3$5496439d@news.astraweb.com> References: <54216c8e$0$29966$c3e8da3$5496439d@news.astraweb.com> <5422ae8b$0$29980$c3e8da3$5496439d@news.astraweb.com> From: Ian Kelly Date: Wed, 24 Sep 2014 08:26:46 -0600 Subject: Re: GCD in Fractions To: Python Content-Type: text/plain; charset=UTF-8 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: 34 NNTP-Posting-Host: 2001:888:2000:d::a6 X-Trace: 1411568850 news.xs4all.nl 2868 [2001:888:2000:d::a6]:58270 X-Complaints-To: abuse@xs4all.nl Xref: csiph.com comp.lang.python:78289 On Wed, Sep 24, 2014 at 5:44 AM, Steven D'Aprano wrote: > The Collins Dictionary of Mathematics (second edition, 2002) says: > > highest common factor, greatest common factor, or greatest > common divisor (abbrev hcf, gcf, gcd) > > n, an integer d that exactly divides (sense 2) two given > integers a and b, and is such that if c divides a and b, > then c divides d; this definition extends to finite sets > of integers and to integral domains. For example, the > highest common factor of 12, 60 and 84 is 12. > > Yet again, we have no clear definition for negative values. Well, this definition would imply that gcd(a, b) should always return *two* results, one positive and one negative. I don't think anybody wants that. It would make more sense to standardize on one of them, and if we take sqrt as an example, then the result should be positive. > Here's an example using Euclid's algorithm to calculate the GCD of negative > numbers, and sure enough, you get a negative result: > > https://answers.yahoo.com/question/index?qid=20111021023909AA8bCjB This depends entirely on your implementation of the modulo operation, which is an issue of computing since the operator is not used in mathematics. The algorithm itself only specifies at each step to solve the equation R_{n-2} = Q * R_{n-1} + R_{n}, such that |R_{n}| < |R_{n-1}|. For any given input there can be many possible solutions, both positive and negative, regardless of the signs of the inputs, and it doesn't matter which solution you choose. So one could implement Euclid's algorithm to return either a positive or negative result for any arbitrary pair of integers.