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.

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

Tags: algorithms

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:

And a looped version.

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:thanks but ...How can i know wich code is faster? Generally how to that in Python?timeit.Use the timeit module: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?

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