Euclid's Algorithm in Python?

[mensanator at aol.com]

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