\ Knuth's Algorithm E, TAOCP, Fundamental Algorithms, page 15. \ Extended Euclid's Algorithm; d = gcd(m,n) = a*m + b*n \ --------------------------------------------------- \ (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 ) 0 1 1 0 0 LOCALS| q x x' y y' gcd c | BEGIN c gcd /MOD ( -- r q ) OVER WHILE gcd TO c TO q TO gcd x' x TO x' x q * - TO x y' y TO y' y q * - TO y REPEAT 2DROP gcd x y ;