Extended Euclidean Algorithm in Python (Without recurrsion)

egcd.py

#!/usr/bin/python3

import math

# Taken in part from: https://www.geeksforgeeks.org/python-program-for-basic-and-extended-euclidean-algorithms-2/
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
    See: https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm

    Parameters:
    a (int): The first number
    b (int): The second number

    Returns:
    (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])))
    else:
        for line in sys.stdin:
            print (gcdExtended(*map(int, line.split())))