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@unpythonic.net]

Re: Euclid's Algorithm in Python?

Well, this article

http://pythonjournal.cognizor.com/pyj1/AMKuchling_algorithms-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)

iD8DBQFC8tQQJd0 1MZaTXX0RAo6iAJ 9JUzRbQ4Cvthgp9 +pr3MHGiER/tACgl5rQ
bbHUVwSg5xRPhWd RAINbMTQ=
=Ah8K
-----END PGP SIGNATURE-----

[Jordan Rastrick]

Re: Euclid's Algorithm in Python?

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....

jepler@unpython ic.net wrote:[color=blue]
> 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[/color]

[Antoon Pardon]

Re: Euclid's Algorithm in Python?

Op 2005-08-05, Jordan Rastrick schreef <jrastrick@stud ent.usyd.edu.au >:[color=blue]
> 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).[/color]

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

--
Antoon Pardon

[jepler@unpythonic.net]

Re: Euclid's Algorithm in Python?

On Thu, Aug 04, 2005 at 08:13:11PM -0700, Jordan Rastrick wrote:[color=blue]
> 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:[/color]
[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)

iD8DBQFC85WLJd0 1MZaTXX0RAsS9AJ 0dbdmXeQoM1Axnp XfRa+X1fAwtWgCg oxmA
C0BvGhd+MIkNefE c+bEnIic=
=iTav
-----END PGP SIGNATURE-----

[Erik the Red]

Re: Euclid's Algorithm in Python?

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]

Re: Euclid's Algorithm in Python?

Erik the Red wrote:[color=blue]
> 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?[/color]

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]

Re: Euclid's Algorithm in Python?

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]

Re: Euclid's Algorithm in Python?

On 7 Aug 2005 17:31:02 -0700, "Jordan Rastrick" <jrastrick@stud ent.usyd.edu.au > wrote:
[color=blue]
>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.
>[/color]
what is the convention for handling signed arguments? E.g.,
[color=blue][color=green][color=darkred]
>>> def gcd(a,b):[/color][/color][/color]
... while b != 0:
... a, b = b, a%b
... return a
...[color=blue][color=green][color=darkred]
>>> gcd(3, -12)[/color][/color][/color]
-3[color=blue][color=green][color=darkred]
>>> gcd(-12, 3)[/color][/color][/color]
3

Regards,
Bengt Richter

[mensanator@aol.com]

Re: Euclid's Algorithm in Python?


Erik the Red wrote:[color=blue]
> 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?[/color]

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 ZeroDivisionErr or 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
[color=blue][color=green][color=darkred]
>>> A=collatz_funct ions.gmpy.divm( 69544657471,351 84372088832,196 83)
>>> A[/color][/color][/color]
mpz(15242)

Checking,
[color=blue][color=green][color=darkred]
>>> G = divmod(35184372 088832*15242-69544657471,196 83)
>>> G[/color][/color][/color]
(27245853265931 L, 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]

Re: Euclid's Algorithm in Python?

On 2005-08-08, Bengt Richter <bokr@oz.net> wrote:[color=blue]
> On 7 Aug 2005 17:31:02 -0700, "Jordan Rastrick" <jrastrick@stud ent.usyd.edu.au > wrote:
>[color=green]
>>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.
>>[/color]
> what is the convention for handling signed arguments? E.g.,[/color]

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@aol.com]

Re: Euclid's Algorithm in Python?


Antoon Pardon wrote:[color=blue]
> On 2005-08-08, Bengt Richter <bokr@oz.net> wrote:[color=green]
> > On 7 Aug 2005 17:31:02 -0700, "Jordan Rastrick" <jrastrick@stud ent.usyd.edu.au > wrote:
> >[color=darkred]
> >>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.
> >>[/color]
> > what is the convention for handling signed arguments? E.g.,[/color]
>
> As far as I understand the convention is it doesn't make
> sense to talk about a gcd if not all numbers are positive.[/color]

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.
[color=blue]
>
> I would be very interested if someone knows what the gcd
> of 3 and -3 should/would be.[/color]

Someone has already decided what it should be.
[color=blue][color=green][color=darkred]
>>> from gmpy import *
>>> help(gcd)[/color][/color][/color]
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)
[color=blue][color=green][color=darkred]
>>> gcd(3,-3)[/color][/color][/color]
mpz(3)


What would really be interesting is whether this conflicts with
any other implementation of GCD.
[color=blue]
>
> --
> Antoon Pardon[/color]

[James Dennett]

Re: Euclid's Algorithm in Python?

Antoon Pardon wrote:
[color=blue]
> On 2005-08-08, Bengt Richter <bokr@oz.net> wrote:
>[color=green]
>>On 7 Aug 2005 17:31:02 -0700, "Jordan Rastrick" <jrastrick@stud ent.usyd.edu.au > wrote:
>>
>>[color=darkred]
>>>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.
>>>[/color]
>>
>>what is the convention for handling signed arguments? E.g.,[/color]
>
>
> 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.[/color]

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