See http://en.wikipedia.org/wiki/Euclidean_algorithm for Algol-style pseudocode.


1. Looped Euclidean algorithm by division

: gcd-by-division ( x y -- z ) [ 2dup [ zero? ] either? ] [ tuck mod ] until drop ;


2. Looped Euclidean algorithm by subtraction

: gcd-by-subtraction ( x y -- z ) [ 2dup [ zero? ] either? ] [ 2dup > [ tuck ] [ over ] if - ] until drop ;


3. Recursive Euclidean algorithm by subtraction
  (This version modeled on suggestion by Slava.)

: done? ( x y -- ? ) 2dup [ zero? ] either? ;
: step ( x y -- x' y' ) 2dup > [ tuck ] [ over ] if - ;
: gcd-by-subtraction ( x y -- z ) done? [ drop ] [ step gcd-by-subtraction ] if ;