Skip to content

Instantly share code, notes, and snippets.

Last active February 18, 2021 08:48
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
What would you like to do?
Extended Euclidean Algorithm in Python (Without recurrsion)
import math
# Taken in part from:
def gcdExtended(a, b):
Calculates the GCD of the two given numbers, as well as the coefficients x and y
such that ax + by = gcd(a,b). This is useful in cryptography
a (int): The first number
b (int): The second number
(int, int, int): The GCD, x, y
stack = [0] * 5 * int(1 + math.log10(min(a, b)))
ptr = 0
while a != 0:
ptr -= 1
stack[ptr] = b // a
a, b = b % a, a
gcd = b
x, y = 0, 1
while ptr != 0:
x, y = y - stack[ptr] * x, x
ptr += 1
return gcd, x, y
if __name__ == '__main__':
import sys
if len(sys.argv[1:]) == 2:
print (gcdExtended(int(sys.argv[1]), int(sys.argv[2])))
for line in sys.stdin:
print (gcdExtended(*map(int, line.split())))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment