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, 10 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, 10 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, 10 months ago

The egcd() method that he provides is actually (i, j, d) and not (d, i, j). Steven Bethard 15 years, 10 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, 10 months ago

thanks but ... How can i know wich code is faster? Generally how to that in Python? Steven Bethard 15 years, 10 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, 10 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, 10 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)