# euclid

2006-09-19

## Introduction

This program implements Euclid's algorithm for determining the greatest common divisor of two natural numbers. It demonstrates function definitions, early returns, and some integer arithmetic. The algorithm is implemeted recursively in languages that are properly tail-recursive1, and iteratively in other languages.

Euclid's algorithm works as follows: to determine the greatest common
divisor of two numbers, call the largest one `x`

and the
smallest one `y`

. Let `m`

be the remainder after
dividing `x`

by `y`

. If `m`

is
`0`

, `y`

completely divides `x`

, and is
thus the greatest common divisor of `x`

and `y`

.
Otherwise, the greatest common divisor of `x`

and
`y`

is equal to the greatest common divisor of `y`

and `m`

.

The above description of the algorithm is recursive: it calls itself.
Moreover, it is tail-recursive, because the result of the recursive call
is also the result of the whole algorithm. Some languages are properly
tail-recursive, meaning that tail-recursive algorithms run in bounded
space. For those languages, the algorithm will be implemented as
specified above. For languages in which tail-recursion is not guaranteed
to run in bounded space, the algorithm is modified to use a loop
which sets `x`

to `y`

and `y`

to
`m`

, instead of a recursive call.

In all cases, the first thing the implementation does is check if
`x`

is less than `y`

. If so, it recursively calls
itself with `x`

and `y`

exchanged, and performs an
early return using the resulting value.

## C

An implementation of Euclid's algorithm is given below.

```
#include <stdio.h>
int euclid(int x, int y) {
int m;
if(x < y) return euclid(y, x);
while(1) {
m = x % y;
if(m == 0) break;
else {
x = y;
y = m;
}
}
return y;
}
int main(int argc, char **argv) {
printf("%d\n%d\n%d\n",
euclid(11, 7),
euclid(7, 11),
euclid(33, 27));
return 0;
}
```

As C is not properly tail-recursive, this
implementation is iterative. C uses infix notation for arithmetic and
comparisons, with `x % y`

representing the modulo
operation.

The program contains 56 words.

## OCaml

The following program works for OCaml:

```
open Printf
let rec euclid x y =
if x < y then (euclid y x)
else let m = x mod y in
if m = 0 then y
else (euclid y m)
let _ = printf "%d\n%d\n%d\n"
(euclid 11 7) (euclid 7 11) (euclid 33 27)
```

Since OCaml is properly tail-recursive, we've
implemented the tail-recursive version of Euclid's algorithm. OCaml
uses infix operators for comparison and arithmetic, with ```
x mod
y
```

calculating `x`

modulo `y`

.

Note that `euclid`

is defined with `let rec`

,
rather than the regular `let`

. This is necessary, because the
regular let doesn't make the bindings it defines visible inside itself,
which would mean that `euclid`

could not call itself.

The program contains 48 words.

## Ruby

This is an implementation of Euclid's algorithm in Ruby:

```
def euclid x, y
return euclid(y, x) if x < y
while true
m = x % y
break if m == 0
x = y
y = m
end
y
end
puts euclid(11, 7), euclid(7, 11), euclid(33, 27)
```

Like C, Ruby is not properly tail recursive and uses
infix notation for arithmetic, with `%`

being used for the
modulo operation. In Ruby, many control flow constructs have two forms,
here illustrated using `if`

:

`expr if test`

and

`if test expr … end`

The first one arguably reads more naturally, but allows
only a single expression. The second form allows one or more
expressions. Besides `if`

, this also applies to
`unless`

, `while`

, and `until`

.

The program contains 39 words.

## Common Lisp

The following is one of many plausible ways to implement Euclid's algorithm in Common Lisp:

```
(defun euclid (x y)
(if (< x y) (return-from euclid (euclid y x)))
(loop for m = (mod x y)
until (= m 0)
do (psetf x y y m)
finally (return y)))
(format t "~A~%~A~%~A~%"
(euclid 11 7) (euclid 7 11) (euclid 33 27))
```

Although many implementations of Common Lisp perform tail call optimization, the language specification does not mandate it, so we've chosen to implement Euclid's algorithm iteratively.

One of the striking characteristics of Common Lisp is that it
consistently uses prefix notation, also for comparisons and arithmetic.
Thus, we get `(< x y)`

and `(mod x y)`

, etc.

Most of the work is done inside the `loop`

form. The Loop
Facility is really a language within a language, which looks like a
mixture of English and Lisp. Of course, it isn't really English, but the
fact that it looks like English means that code that
uses `loop`

is often easier to read than equivalent code that
doesn't. The fact that the Loop Facility can be implemented as a macro
in Common Lisp really shows how powerful Lisp macros are.

In the above program, each iteration of the `loop`

form
first sets `m`

to the modulo of `x`

and
`y`

. It then checks if `m`

equals `0`

,
leaving the loop if this is the case. Leaving the loop causes the
`finally`

clause to be executed, which means that
`y`

is returned (from the loop, and subsequently from the
function).

As long as the loop runs, the code after the `do`

clause
is executed. `(psetf x y y m)`

sets `x`

to
`y`

and `y`

to `m`

, in parallel, so
that `x`

gets the value of `y`

before it was
updated.

A final thing to note about the code above is the use of
`return`

vs. `return-from`

.
`Return-from`

takes two arguments: the name of the body to
return from, and the value to return (which is actually optional; if not
specified, `nil`

is returned). `defun`

defines a
body with the same name as the function it defines; in this case,
`euclid`

. Hence `(return-from euclid …)`

.
`loop`

(as well as other iteration forms in Common Lisp) also
defines a body, but it doesn't have name. `(return …)`

returns `…`

(`nil`

if not specified) from
the innermost anonymous block, and is actually equivalent to
`(return-from nil …)`

.

This implementation of Euclid's algorithm contains 45 words.

1 A properly tail-recursive language is one that optimizes tail-recursive algorithms so that the recursion doesn't cause them to run out of space. An algorithm is tail-recursive when the recursive calls happen in tail position. This means that the function that performs the recursive call will immediately return the value returned by the recursive call, without doing anything else. Euclid's algorithm is an example of a tail recursive algorithm.