Euclid's Extended Algorithm
Join the DZone community and get the full member experience.Join For Free
Basically Euclid's algorithm for finding the largest common denominator, this one is modified in order to obtain the numbers d, x, y, where d is the dennominator and they check the following equation: d = ax + by
def euclidExtended(a, b): if b == 0: return a, 1, 0 dd, xx, yy = euclidExtended(b, a % b) d, x, y = dd, yy, xx - int(a / b) * yy return d, x, y
Opinions expressed by DZone contributors are their own.