# Paste: Three Euclidean implementations of gcd

Author: | Loryn |

Mode: | factor |

Date: | Wed, 8 Apr 2009 14:05:27 |

Plain Text |

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 ;

## New Annotation