euclid

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.