Euclidean algorithm (Forth)

From LiteratePrograms

Other implementations: C | Erlang | Forth | Haskell | Java | Java, recursive | OCaml | 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)

Download code