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) ``` Alexander Ross 15 years, 8 months ago

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

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

The egcd() method that he provides is actually (i, j, d) and not (d, i, j). Steven Bethard 15 years, 8 months ago

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

thanks but ... How can i know wich code is faster? Generally how to that in Python? Steven Bethard 15 years, 8 months ago

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

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

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)

### Required Modules

• (none specified)