Euclid's Algorithm in Python?

[Erik the Red]

In Fundamental Algorithms (The Art of Computer Programming), the first
algorithm discussed is Euclid's Algorithm.

The only idea I have of writing this in python is that it must involve
usage of the modulo % sign.

How do I write this in python?

[jepler]

Well, this article
http://pythonjournal.cognizor.com/py...rithms-V1.html
was the first hit on google for '"euclid's algorithm" python'.

It contains this function:
def GCD(a,b):
assert a >= b # a must be the larger number
while (b != 0):
remainder = a % b
a, b = b, remainder
return a

Jeff

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.6 (GNU/Linux)

iD8DBQFC8tQQJd01MZaTXX0RAo6iAJ9JUzRbQ4Cvthgp9+pr3M HGiER/tACgl5rQ
bbHUVwSg5xRPhWdRAINbMTQ=
=Ah8K
-----END PGP SIGNATURE-----

[Jordan Rastrick]

Raising an assertion error for a < b is a bit of overkill, since its
not really a case of bad input. So normally you see Euclid done like
this:

def gcd(a,b): # All lowercase for a function is a bit more
conventional.
if a < b:
a, b = b, a # Ensures a >= b by swapping a and b if nessecary
while b != 0: # Note parentheses are unnessecary here in python
a, b = b, a % b
return a

A bit more concise and no less readable (IMO).

If you really want to check for actual bad input, youre better off
testing, for example, than a and b are both greater than 0....

je****@unpythonic.net wrote:

Well, this article
http://pythonjournal.cognizor.com/py...rithms-V1.html
was the first hit on google for '"euclid's algorithm" python'.

It contains this function:
def GCD(a,b):
assert a >= b # a must be the larger number
while (b != 0):
remainder = a % b
a, b = b, remainder
return a

Jeff

[Antoon Pardon]

Op 2005-08-05, Jordan Rastrick schreef <jr*******@student.usyd.edu.au>:

Raising an assertion error for a < b is a bit of overkill, since its
not really a case of bad input. So normally you see Euclid done like
this:

def gcd(a,b): # All lowercase for a function is a bit more
conventional.
if a < b:
a, b = b, a # Ensures a >= b by swapping a and b if nessecary
while b != 0: # Note parentheses are unnessecary here in python
a, b = b, a % b
return a

A bit more concise and no less readable (IMO).

The if test is unnecessary. Should a be smaller than b, the two values
will be swapped by the while body.

--
Antoon Pardon

[jepler]

On Thu, Aug 04, 2005 at 08:13:11PM -0700, Jordan Rastrick wrote:

Raising an assertion error for a < b is a bit of overkill, since its
not really a case of bad input. So normally you see Euclid done like
this:

[snipped]

My point was not so much that this was the ultimate implementation of GCD, but
that the obvious search would have turned up many enlightening results,
including the topmost one.

Jeff

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.6 (GNU/Linux)

iD8DBQFC85WLJd01MZaTXX0RAsS9AJ0dbdmXeQoM1AxnpXfRa+ X1fAwtWgCgoxmA
C0BvGhd+MIkNefEc+bEnIic=
=iTav
-----END PGP SIGNATURE-----

[Erik the Red]

So, I did the following:
---
a=input("Give me an integer")
b=input("Give me another integer")

def gcd(a,b):

if a < b:
a, b = b, a
while b != 0:
a, b = b, a % b
return a
---
But, in the xterm, it terminates after "Give me another integer."

Is Euclid's Algorithm supposed to be implemented in such a way as to be
used as a tool to find the GCD of two integers, or have I
misinterpreted the intent of the algorithm?

[Reinhold Birkenfeld]

Erik the Red wrote:

So, I did the following:
---
a=input("Give me an integer")
b=input("Give me another integer")

def gcd(a,b):

if a < b:
a, b = b, a
while b != 0:
a, b = b, a % b
return a
---
But, in the xterm, it terminates after "Give me another integer."

Is Euclid's Algorithm supposed to be implemented in such a way as to be
used as a tool to find the GCD of two integers, or have I
misinterpreted the intent of the algorithm?

You do not do anything after both input() calls. You define the function, but
never call it.

Add
print gcd(a, b)
to the end and it will print your result.

Note that the variable names a and b in the function don't have anything to
do with your two input variables.

Reinhold

[Jordan Rastrick]

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.

[Bengt Richter]

On 7 Aug 2005 17:31:02 -0700, "Jordan Rastrick" <jr*******@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.,

def gcd(a,b): ... while b != 0:
... a, b = b, a%b
... return a
... gcd(3, -12) -3 gcd(-12, 3)

3

Regards,
Bengt Richter

[mensanator]

Erik the Red wrote:

So, I did the following:
---
a=input("Give me an integer")
b=input("Give me another integer")

def gcd(a,b):

if a < b:
a, b = b, a
while b != 0:
a, b = b, a % b
return a
---
But, in the xterm, it terminates after "Give me another integer."

Is Euclid's Algorithm supposed to be implemented in such a way as to be
used as a tool to find the GCD of two integers, or have I
misinterpreted the intent of the algorithm?

Personally, I would just use a math library that includes GCD and
probably does it more efficiently that I could. An example of
which is GMPY, the GNU Multiple Precision C library with a
Python wrapper.

But if I wanted to roll my own, I would implement the Extended
Euclidean Algorithm which produces some usefull information that
can be used to solve a Linear Congruence in addition to finding
the GCD. A Linear Congruence would be

X*A = Z (mod Y) where "=" means "is congruent to".

Given X, Y and Z, A can be solved IIF GCD(X,Y) divides Z. If you
use the Extended Euclidean Algorithm to find GCD(X,Y) you will
have the additional parameters needed to solve the Linear
Congruence (assuming it is solvable).

For example, I run into problems of the form

G = (X*A - Z)/Y

where I want to find an integer A such that G is also an integer
(X, Y and Z are integers). Lucky for me, the RHS can be directly
converted to a Linear Congruence: X*A = Z (mod Y). And in my
particular problems, X is always a power of 2 and Y always a
power of 3 so the GCD(X,Y) is always 1 which will always divide
Z meaning my problems are _always_ solvable.

And GMPY has a function that directly solves Linear Congruence:

divm(a,b,m): returns x such that b*x==a modulo m, or else raises
a ZeroDivisionError exception if no such value x exists
(a, b and m must be mpz objects, or else get coerced to mpz)

So the first integer solution to

35184372088832*A - 69544657471
------------------------------
19683

is

A=collatz_functions.gmpy.divm(69544657471,35184372 088832,19683)
A mpz(15242)

Checking,
G = divmod(35184372088832*15242-69544657471,19683)
G

(27245853265931L, 0L)

Of course, what the gods give they also take away. It turns out
that the GMPY divm() function has a bug (whether in the underlying
GMP C code or the Python wrapper I don't know). It has a memory
leak when called repeatedly with large numbers making it useless
to me. But I caught another lucky break. GMPY also provides a
modulo inverse function from which one can easily derive the
linear congruence. And this function doesn't exhibit the memory
leak.

But luck favors the prepared mind. I was able to come up with a
workaround because I had gone to the trouble of working up an
Extended Euclidean Algorithm prior to discovering that I didn't
need it. But during the course of which, I also learned about
modulo inverse which was the key to the workaround.

[Antoon Pardon]

On 2005-08-08, Bengt Richter <bo**@oz.net> wrote:

On 7 Aug 2005 17:31:02 -0700, "Jordan Rastrick" <jr*******@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.

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

--
Antoon Pardon

[mensanator]

Antoon Pardon wrote:

On 2005-08-08, Bengt Richter <bo**@oz.net> wrote:

On 7 Aug 2005 17:31:02 -0700, "Jordan Rastrick" <jr*******@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

[James Dennett]

Antoon Pardon wrote:

On 2005-08-08, Bengt Richter <bo**@oz.net> wrote:

On 7 Aug 2005 17:31:02 -0700, "Jordan Rastrick" <jr*******@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.

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

Within the integers, common definitions of gcd don't distinguish
positive from negative numbers, so if 3 is a gcd of x and y then
-3 is also a gcd. That's using a definition of gcd as something
like "g is a gcd of x and y if g|x and g|y and, for any h such
that h|x and h|y, h|g", i.e., a gcd is a common divisor and is
divisible by any other common divisor. The word "greatest" in
this context is wrt the partial ordering imposed by | ("divides").
(Note that "|" in the above is the mathematical use as a|b if
there is an (integral) c such that ac=b, i.e., b is divisible
by a. These definitions generalize to rings other than the
integers, without requiring a meaningful < comparison on the
ring.)

All of that said, it would be reasonable when working in the
integers to always report the positive value as the gcd, to
make gcd a simpler function. For some applications, it won't
matter if you choose positive or negative, so going positive
does no harm, and others might be simplified by assuming gcd>0.

-- James