September 4, 2026

Haskell for Hobos -- Euclid's algorithm

"Who is Euclid?" I hear you ask. He was a clever greek fellow who lived around 300 BC. He is called "the father of geometry". Some people call him the "father of mathematics".

One of many things he is famous for is his algorithm for finding the HCF (highest common factor) of two numbers. This is where "numbers" are natural numbers, i.e. positive integers.

You take the biggest of the two and divide it by the smaller. If the remainder is zero, the smaller is the HCF. If not, replace the big one with the smaller, the smaller with the remainder and repeat the process until you finally get a remainder of zero.

This is an obvious recursion and we can write it in Haskell like this: 

a = 60
b = 45

putShow = putStrLn . show

euclid x 0 = x
euclid x y = euclid y r
    where r = mod x y

main = putShow $ euclid a b
This "euclid" function performs an extra step if b is greater than a. Perhaps it should guard against a zero first argument? It doesn't seem to do any harm.

Some background

I first encountered Euclid's algorithm when I started reading Donald Knuth's books "The Art of Computer Programming". He pretty much launches the books by examining Euclid's algorithm. Not without good reason -- people say it is the oldest algorithm that we have any record of.

Knith first studied Physics at Case Institute of Technology. He switched from physics to mathematics and got two mathematics degrees from Case. He went on to earn a PhD in mathematics at the California Institute of Technology (Cal Tech) with a thesis entitled "Finite Semifields and Projective Planes".

I find it useful to understand his foundation and background in Mathematics. I have sometimes been frustrated by his work in Computer Science, but can warm up to him as a mathematician.

He launches his first book, "Fundamental Algorithms" with Euclids Algorithm, introducing it on page 2. He goes on to give a proof. He visits it again in the second book, "Seminumerical Algorithms" beginning a discussion on page 316. (These page numbers refer to my second edition)

Euclids algorithm often shows up and is discussed in introductory books on number theory such as "The Higher Arithmetic" by H. Davenport (on page 25).

The original algorithm was defined in terms of successive subtraction. Defining it in terms of division, as we have here, is called the "extended Euclids algorithm".

I have found it relatively easy to be convinced that the method works, providing a common factor. To be convinced that it yields the highest common factor is actually not too hard.

The first step yields the remainder r from a and b such that a - b*x = r. A common factor of a and b must divide both a and b by definition. So it must also divide r = a - b*x. This is true of all factors of a and b, which must also include the greatest one.

An interesting question is whether there is a bound on the number of steps required for the algorithm to converge.

Have any comments? Questions? Drop me a line!

Tom's software pages / tom@mmto.org