extended great common divisor function (Python recipe) by Robert W. Hanks

ActiveState Code (http://code.activestate.com/recipes/474129/)

These might be a little more efficient. These are two implementations of the Euclidean algorithm, which is probably the most efficient for finding the GCD of two integers a and b.

A recursive version:

def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

And a looped version.

def gcd1(a, b):
    while a != b:
        if a > b:
            a = a - b
        else:
            b = b - a
    return a

Perhaps, but the point of the _extended_ euclid GCD function is to find a multiplicative inverse.

Say a and b are coprime, and (d, i, j) = egcd(a,b). d will be 1, and (a*i)%b == 1 . This is a very useful calculation for the RSA cryptosystem.

The egcd() method that he provides is actually (i, j, d) and not (d, i, j).

alternate version. I don't know if this is more efficient, but following the code in http://www.geocities.com/hjsmithh/Numbers/GCDe.html gives me:

def egcd(a, b):
    u, u1 = 1, 0
    v, v1 = 0, 1
    g, g1 = a, b
    while g1:
        q = g // g1
        u, u1 = u1, u - q * u1
        v, v1 = v1, v - q * v1
        g, g1 = g1, g - q * g1
    return u, v, g

thanks but ... How can i know wich code is faster? Generally how to that in Python?

timeit. Use the timeit module:

$ cat > egcd1.py
def egcd(a,b):  # a > b > 0
    """ Extended great common divisor, returns x , y
        and gcd(a,b) so ax + by = gcd(a,b)       """

    if a%b==0: return (0,1,b)
    q=[]
    while a%b != 0:
        q.append(-1*(a//b))
        (a,b)=(b,a%b)
    (a,b,gcd)=(1,q.pop(),b)
    while q:(a,b)=(b,b*q.pop()+a)
    return (a,b,gcd)

$ cat > egcd2.py
def egcd(a, b):
        u, u1 = 1, 0
        v, v1 = 0, 1
        g, g1 = a, b
        while g1:
                q = g // g1
                u, u1 = u1, u - q * u1
                v, v1 = v1, v - q * v1
                g, g1 = g1, g - q * g1
        return u, v, g
$ python -m timeit -s "from egcd1 import egcd; nums = xrange(1, 100)" "[egcd(x, y) for x in nums for y in nums]"
10 loops, best of 3: 89.5 msec per loop
$ python -m timeit -s "from egcd2 import egcd; nums = xrange(1, 100)" "[egcd(x, y) for x in nums for y in nums]"
10 loops, best of 3: 77 msec per loop

If I didn't screw that up, it looks like my version's slightly faster.

thanks. thanks you, your version is a lot faster. why to use g ang g1?

this is better isn't it?

def egcdweb1(a,b):
    u, u1 = 1, 0
    v, v1 = 0, 1
    while b:
        q = a // b
        u, u1 = u1, u - q * u1
        v, v1 = v1, v - q * v1
        a, b = b, a - q * b
    return u, v, a

That's fine too of course. I was just trying to be as faithful as possible to the link I referenced.