Euclid’s Ancient Recipe
The oldest algorithm still in use which dates back over two thousand years
Algorithms are one of the most important concepts in all of computer science. What they are and how they work are essential to any understanding of the subject. But the concept of an algorithm had to be carefully worked out mathematically. It wasn’t simply found when some mathematician looked under the correct rock.
When the trailblazers of computer science first began to try and fully nail down the idea of an algorithm they had at least an intuitive understanding of algorithms. They even had examples to analyse, the most famous of which was Euclid’s algorithm, which has been called the “granddaddy of all algorithms.” It was written over two thousand years ago by the Greek mathematician Euclid, and is the oldest known algorithm still in use. It’s a procedure for finding the greatest common divisor (GCD) of two whole numbers — the largest number which divides both of numbers without leaving a remainder.
If we say that a and b represent two whole numbers, then the algorithm goes like this:
Step 1: Divide a by b. Assign the remainder of the division to r.
Step 2: If r is 0 then output b is the greatest common divisor and halt.
Step 3: Otherwise, assign the value of b to a (a ← b).
Step 4: Assign the value of r to b (b ← r).
Step 5: Go back to step 1.
(One thing to note: a, b and r are variables. That’s to say they’re each placeholders for some value that can repeatedly change over time. If a value has already been assigned to that variable, the new value replaces it.)
That’s a black-and-white description. But humans, whether they’re computer scientists or not, tend to understand pictorial representations easier than text. One can use a tool called a flow chart to help with comprehension of an algorithm. A flow chart shows the flow of steps through an algorithm making things easier to understand. The flow chart of Euclid’s algorithm is below.
The person who called Euclid’s Algorithm as “the granddaddy of all algorithms” was Donald Knuth. If anyone deserves the title of computer science’s unofficial historian, no-one does more so than Donald Knuth. His great contribution to the field includes his epic work on programming theory and practice, The Art of Computer Programming. The depth of this work is astounding; programs, equations, charts and tables litter almost every page of the book. Single chapters are typically over 200 pages long. The attention to detail verges on the obsessive. So seriously does Knuth take the issue of accuracy that he offers a reward for every error found in his books…a cheque for $2.56. But he doesn’t have to worry about losing too much money — not only is his material extremely polished, but many recipients of the reward choose not to cash the cheque. So highly is Knuth regarded, they prefer to keep it as a memento.
Strictly speaking, Knuth’s work is incomplete. He began The Art of Computer Programming in 1962, conceiving of it as a single ten-chapter book. Within a few years, his project had ballooned into a planned five-volume series. As of 2015, he has fully completed three of the five books, the fourth is underway, and the fifth is expected to come out in 2020 when he will be 82 years old.
Professor Knuth, it seems, is a thorough individual.
Knuth deals with the concept of algorithms early his book and for good reason. The algorithm was a critical breakthrough in the development of computer science and remains a cornerstone of the discipline. In introducing us to the algorithm, Knuth shows that it had an unclear history. The word itself came to us through a series of linguistic corruptions and redefinitions over the years. Indeed, it didn’t even appear in Webster’s dictionary until 1957, which is not to say it held no prior meaning. Before that, mathematicians and computer scientists would have broadly held to definitions such as “a set of rules for solving a mathematical problem in a finite sequence of steps”. But what does that mean?
It’s useful when learning about algorithms to know what informal ideas are behind them. These are the same ideas that people had when they began to investigate algorithms. It’s now almost a cliché to use a cooking recipe as an analogy for algorithms to introduce someone to the concept. I must confess that when something is clichéd it makes me nervous to use it. Still, I can’t find a better way…and Donald Knuth uses it too. If it’s good enough for him, it’s good enough for me.
When cooking, you start off with a set of ingredients (input), you prepare them in a specific way (process), and the result is, hopefully, a tasty dish (output). As with computation, there is some interesting work to be done in the first and last stages, but the hardest work is the middle (processing) part, which is also where the key to our analogy lies.
It’s a far-from-perfect analogy, but still a very good explanation for the uninitiated. Furthermore, some of the imperfections in the analogy help illustrate some important features about algorithms. The following are the key points.
Characteristics
A recipe is a list of instructions that you must follow. Each instruction we can refer to as a step. Most of the steps tell you to undertake some work that alters the state of your ingredients, although not all of them do. Occasionally, the recipe might direct you to pre-heat your oven or clean your chopping board. These steps don’t deal with ingredients, but refer to your cooking environment and are essential to the process.
This aligns very nicely with the description of an algorithm, which is also a list of instructions, each of which causes some change in the environment. Similarly, each step of an algorithm often works with the input parameters (recipe ingredients), but not always.
Clarity
The chef, the author of the recipe, will strive to make the instructions as clear as possible. If the recipe is unclear, the risk of doing something wrong increases and, to put it politely, you get “incorrect output”.
Now this is where the analogy with algorithms is not as strong. When the chef writes a recipe, each step should be written so it is easy to understand; precise amounts should be used and exact times given. Nevertheless, there will always be scope for misinterpretation and error. Recipes might refer to a “pinch of salt” or a “dash of pepper”, or instruct the reader to “mix until it runs smoothly”. Notwithstanding the fact that cooking requires experience before your output is reliably successful, there’s another problem. Recipes are expressed in natural language, which makes it very difficult to compose an unambiguous sentence. One of my favourite examples of this is “fruit flies like a banana.” Is this line a comment on the fructal preferences of Drosophilidae or on the aerodynamics of all fruits compared with bananas?
I love the endless flexibility of natural language as much as any writer or poet, but there is no place for it in algorithms. As you will see later, each step of an algorithm has to be definite. It must have only one possible meaning that is understandable to anyone.
Sequence
Almost too trivial to point out, but still essential, is that the steps of both a recipe and an algorithm must be carried out in sequence. This is because they both deal with state. In the case of the recipe, it is the state of the kitchen and the food. In the case of the algorithm, it is the state of the data. The result of each step depends on the current state. Dicing an onion and frying an onion are different steps. Dicing an onion before you fry it has a different outcome than the reverse. Similarly, multiplying a number by 2 then adding 5 yields a different result than adding 5 then doubling it. Like a recipe, you must respect the sequence when running through an algorithm for it to have a meaningful result.
That doesn’t mean you can’t do some steps at the same time and have some choice over which step to carry out next, but I’m saving that for the later chapter about concurrency.
Iteration
Let’s say you’re cutting cookies out of some dough that you’ve rolled out. There’s enough dough to make a dozen cookies and you have to put each cookie onto a baking tray. It is doubtful the recipe will read something like this…
- Cut the first cookie from the dough
- Lay it on the baking tray
- Cut the second cookie from the dough
- Lay it on the baking tray
- Cut the third cookie from the dough
…and so on. While this accurately describes what you have to do, you’re smart enough (I hope) that you don’t need every single step of a repeated piece of work explicitly described to you. It’s enough to have a single step that reads something like “Cut twelve cookies from the dough. Lay each cookie onto the baking tray”, which is equivalent to the 24 steps it would replace.
This is an example of iteration, a very useful tool when you have a single action that needs to be applied to each item in a collection of things. The exact same thing appears in algorithms, because we often want to repeat a series of steps and need a concise way of expressing it. Conciseness is one aspect, but there’s an additional point that the cookie example doesn’t convey. I admit it’s unrealistic for a recipe to specify the exact number of cookies to cut. More likely, it will instruct you to keep cutting until the dough is all used up. Adding a condition like this (the part of the sentence that’s emphasised) makes iteration all the more powerful because it’s more general. The situation may vary from person to person (like the exact amount of dough), but the algorithm still works.
Decision-making
While we’re on the subject of generality, there’s an essential property of any set of instructions (recipes and algorithms included) which is the ability to make decisions based on circumstances. For example, any cook will know that you have to do things differently depending on what type of oven you have. Gas ovens need cooking temperatures expressed in gas marks and convection ovens usually need shorter cooking times. Rather than print multiple versions of a recipe for each type of oven (which would be identical except for the steps dealing with cooking temperatures and times), the steps describing what to do when putting your food in the oven will tell you to make a decision based on circumstances. The author of the recipe has no idea which oven you have, but provides different temperatures and cooking times for every type of oven they know.
For algorithms, this is called selection. Like iteration, selection is a fundamental way to make an algorithm more powerful.
When you go back and read Euclid’s algorithm again, you should recognise at least some of the characteristics I outlined earlier. The algorithm is a sequence of steps which are sufficiently clear to anyone wishing to follow them. It accepts input (the variables a and b) and gives output. Furthermore, it has examples of both iteration and decision-making. At Step 5, we are instructed to jump back to Step 1 and repeat the steps. In Step 2, we’re told to make a decision depending on the current state, which is also where the algorithm terminates and gives its output. Try it yourself. Choose some numbers and go through it with pencil and paper (and maybe a calculator).
You might notice from the flow chart that there is a “loop” in the algorithm. Whenever the test in Step 2 fails, the path through the algorithm returns to the first step (via Step 5). But you might be thinking, what if the test never succeeds (i.e. r, the remainder, is always non-zero)? Won’t the algorithm keep going forever? Luckily, in the case of Euclid’s algorithm, we can rest easy and see that this can’t happen. The values assigned to a and b are continually reduced by the algorithm. Eventually, if no common divisor is found, both a and b will hold the value 1. The remainder of 1 divided by 1 is 0, causing the algorithm execution to halt and inform us that the greatest common divisor is 1. This is the fail safe in Euclid’s algorithm that prevents infinite loops.
Still, any concern about never-ending execution is a genuine worry. Programmers today are constantly on guard against infinite loops because they can really mess up a program. But, as you’ll see in a following article, the concept of a never-ending program had profound consequences for the early pioneers of computer science.
1 The tern “mod” from “a mod b” in the flow chart is a computing shorthand for a remainder division (called modulo). It refers to the remainder when a divided is by b.
