# Euclidean algorithm (Forth)

**Other implementations**: C | Erlang |**Forth**| Haskell | Java | Java, recursive | Prolog | Python | Scala | Standard ML

The Euclidean algorithm is an efficient method for computing the greatest common divisor of two natural numbers (or polynomials, or any other object with the necessary structure), and was one of the first known algorithms to be described formally. It is based on the two identities:

*a*>*b*implies: gcd(*a*,*b*) = gcd(*b*,*a*mod*b*)- gcd(
*a*, 0) =*a*

The Euclidean GCD algorithm is straightforward to describe in Forth using a loop that repeatedly replaces *a* by *b* and *b* by *a* mod *b* while *b* is not zero.

**begin ?dup while ... repeat** executes the loop while the top of the stack is non-zero. **?dup** compared to **dup** does not duplicate the top item if it is zero. It is equivalent to the loop **begin dup while ... repeat drop**.

**tuck** ( a b -- b a b ) copies the top item underneath the second item on the stack. It is equivalent to **swap over**.

**mod** ( a b -- a%b ) takes the modulus of the top two items on the stack.

Together, **tuck mod** does ( a b -- b a%b ).

<<gcd.fs>>=: gcd ( a b -- gcd )begin?dupwhiletuckmodrepeat; \ Some testscr6 10 gcd . \ 2cr10 6 gcd . \ 2 (order doesn't matter)cr10 21 gcd . \ 1 (no factors in common)cr3 0 gcd . \ 3 (allow 0)

Download code |