\  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
;