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 ;