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


cover contents index main page

last modified 8th August 2001
Copyright 2000-2001 Vladimir Zabrodsky
Czech Republic.

mail