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