Euclid's Algorithm in Python?

mensanator at aol.com mensanator at aol.com
Sun Aug 14 17:58:54 CEST 2005


Antoon Pardon wrote:
> On 2005-08-08, Bengt Richter <bokr at oz.net> wrote:
> > On 7 Aug 2005 17:31:02 -0700, "Jordan Rastrick" <jrastrick at student.usyd.edu.au> wrote:
> >
> >>Good point. I suppose I'd only ever seen it implemented with the if
> >>test, but you're right, the plain while loop should work fine. Silly
> >>me.
> >>
> >>def gcd(a,b):
> >>     while b != 0:
> >>           a, b = b, a%b
> >>    return a
> >>
> >>Even nicer.
> >>
> > what is the convention for handling signed arguments? E.g.,
>
> As far as I understand the convention is it doesn't make
> sense to talk about a gcd if not all numbers are positive.

That may well be the convention but I don't know why you say
it doesn't make sense. -3/3 still has a remainder of 0.
So does -3/-3, but 3 is greater than -3 so it "makes sense"
that the GCD will be positive.

>
> I would be very interested if someone knows what the gcd
> of 3 and -3 should/would be.

Someone has already decided what it should be.

>>> from gmpy import *
>>> help(gcd)
Help on built-in function gcd:

gcd(...)
    gcd(a,b): returns the greatest common denominator of numbers a and
b
    (which must be mpz objects, or else get coerced to mpz)

>>> gcd(3,-3)
mpz(3)


What would really be interesting is whether this conflicts with
any other implementation of GCD.

> 
> -- 
> Antoon Pardon




More information about the Python-list mailing list