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

```