Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]


Groups > comp.lang.python > #78289

Re: GCD in Fractions

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 <ian.g.kelly@gmail.com>
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 <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>
From Ian Kelly <ian.g.kelly@gmail.com>
Date Wed, 24 Sep 2014 08:26:46 -0600
Subject Re: GCD in Fractions
To Python <python-list@python.org>
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 <python-list.python.org>
List-Unsubscribe <https://mail.python.org/mailman/options/python-list>, <mailto:python-list-request@python.org?subject=unsubscribe>
List-Archive <http://mail.python.org/pipermail/python-list/>
List-Post <mailto:python-list@python.org>
List-Help <mailto:python-list-request@python.org?subject=help>
List-Subscribe <https://mail.python.org/mailman/listinfo/python-list>, <mailto:python-list-request@python.org?subject=subscribe>
Newsgroups comp.lang.python
Message-ID <mailman.14315.1411568849.18130.python-list@python.org> (permalink)
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

Show key headers only | View raw


On Wed, Sep 24, 2014 at 5:44 AM, Steven D'Aprano
<steve+comp.lang.python@pearwood.info> 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.

Back to comp.lang.python | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread


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