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