\ extended Euclid's algorithm: see Cormen, et al. \ "Algorithms" (MIT Press, 1990) p. 812 \ --------------------------------------------------- \ (c) Copyright 2003 Julian V. Noble. \ \ Permission is granted by the author to \ \ use this software for any application pro- \ \ vided this copyright notice is preserved. \ \ --------------------------------------------------- \ Examples: 99 78 -> 3 -11 14 \ 1769 551 -> 29 5 -16 : xgcd ( a b -- gcd x y) \ gcd = x*a + y*b CR ." xgcd " .S \ display stack on entry DUP 0= ( a b flag) IF 1 SWAP ( -- a 1 0) ELSE TUCK ( b a b) /MOD ( b d'= a mod b [a/b] ) >R ( b d' ) RECURSE ( d' x' y') TUCK R> ( d' y' x' y' a/b) CR ." arrange " .S \ display stack at this step * - ( -- d x y) THEN ( gcd x y) CR ." exit " .S \ display stack on exit ;