Extended Euclid's algorithm
We can compute integers X and Y such as
D=GCD(A,B)=A*X+B*Y
at the same time GCD(A,B) is being calculated.
IMPLEMENTATION
Unit: recursive internal function, external function without procedure statement
Parameters:
a nonnegative integer A, a positive integer B
Interface: the MOD function
Returns: the string of three numbers D X Y separated by blanks. This triple satisfies equation above
EXEUCLID: procedure
parse arg A, B
if B = 0 then return A 1 0
parse value EXEUCLID(B, MOD(A, B)) with D X Y
return D Y (X - (A % B) * Y)
|
EXAMPLE
EXEUCLID(786, 311) returns 1 55 -139
CONNECTIONS
Literature
Knuth D. E., Seminumerical Algorithms, vol. 2 of The Art of Computer Programming
Addison-Wesley, 1973
Cormen T. H., Leiserson Ch. E., Rivest R. L. Introduction to Algorithms
The MIT Press, Cambridge, 1990
