Welcome, guest | Sign In | My Account | Store | Cart

the function find out the gcd(a,b) as a linear conbination of a anb b, ax+by=gcd(a,b). Please help me if you can.

Python, 15 lines
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
 I am new to programing so Is this code ok? how can i make it faster?


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)

8 comments

Alexander Ross 15 years, 8 months ago  # | flag

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
Josiah Carlson 15 years, 8 months ago  # | flag

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.

Josiah Carlson 15 years, 8 months ago  # | flag

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

Steven Bethard 15 years, 8 months ago  # | flag

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
Robert W. Hanks (author) 15 years, 8 months ago  # | flag

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

Steven Bethard 15 years, 8 months ago  # | flag

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.

Robert W. Hanks (author) 15 years, 8 months ago  # | flag

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
Steven Bethard 15 years, 8 months ago  # | flag

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

Created by Robert W. Hanks on Fri, 10 Mar 2006 (PSF)
Python recipes (4591)
Robert W. Hanks's recipes (1)

Required Modules

  • (none specified)

Other Information and Tasks