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 ?dup while tuck mod repeat ; \ Some tests cr 6 10 gcd . \ 2 cr 10 6 gcd . \ 2 (order doesn't matter) cr 10 21 gcd . \ 1 (no factors in common) cr 3 0 gcd . \ 3 (allow 0)