ActiveState Code

Recipe 474129: extended great common divisor function

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

Comments

  1. 1. At 12:49 p.m. on 12 mar 2006, Alexander Ross said:

    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
  2. 2. At 10:05 p.m. on 12 mar 2006, Josiah Carlson said:

    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.

  3. 3. At 10:06 p.m. on 12 mar 2006, Josiah Carlson said:

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

  4. 4. At 10:19 a.m. on 14 mar 2006, Steven Bethard said:

    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
  5. 5. At 1:25 p.m. on 14 mar 2006, Robert W. Hanks (the author) said:

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

  6. 6. At 11:07 a.m. on 15 mar 2006, Steven Bethard said:

    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.

  7. 7. At 3:33 p.m. on 18 mar 2006, Robert W. Hanks (the author) said:

    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
  8. 8. At 9:23 p.m. on 19 mar 2006, Steven Bethard said:

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

Sign in to comment