What an algorithm is

The method for finding the greatest common divisor in Book VII of Euclid's Elements, written about 2,300 years ago, still runs in computers today.

A method that always works

Suppose you need the largest number that divides both 1071 and 462. You could try every number from 462 down to 1 and stop at the first one that divides both. That works, but it may take hundreds of tries. There is a shorter way. Divide 1071 by 462 and keep the remainder, 147. Now divide 462 by 147 and keep the remainder, 21. Divide 147 by 21: the remainder is 0, so the answer is 21. Three divisions instead of several hundred.

That shorter way is an algorithm: a finite list of precise steps that takes some input and produces the right output. This one is Euclid's algorithm for the greatest common divisor, and it appears in Book VII of the Elements, written around 300 BC. Euclid described it with repeated subtraction of lengths rather than division, but the idea is the same, and the version with remainders is what programs use today.

function gcd(a, b) {
  while (b !== 0) {
    const r = a % b;   // remainder
    a = b;
    b = r;
  }
  return a;
}
console.log(gcd(1071, 462)); // 21

What makes a list of steps an algorithm

Textbooks such as the one by Cormen, Leiserson, Rivest and Stein describe an algorithm as a well-defined procedure that turns an input into an output. Three things are packed into that description, and each one matters when you write code.

• Precise. Each step means one thing. "Divide a by b and keep the remainder" is precise; "make the numbers smaller somehow" is not.
• Finite. It must stop. In Euclid's algorithm the remainder is always smaller than the number you divided by, so it shrinks every round and must reach 0.
• Correct. For every allowed input, the output is the right answer, not only for the examples you tried.

A cooking recipe is often given as an everyday example, and it is a fair one: ingredients are the input, the dish is the output, and the steps are in order. The difference is how much the reader fills in. A cook decides what "a pinch" means. A computer decides nothing, which is why algorithms for computers are written with every step spelled out.

Same problem, different algorithms

One problem usually has many correct algorithms, and they can differ enormously in how much work they do. For the greatest common divisor of 1071 and 462, trying every number from 462 downward needs 442 tries before it reaches 21, while Euclid's method needs 3 divisions. Both are correct. Only one is quick. Much of this course is about that second question: once a method is correct, how many steps does it take, and how does that number grow when the input gets bigger?

To answer it, computer scientists count basic steps (a comparison, a swap, a division) rather than seconds. Seconds depend on the machine. A count of steps depends only on the algorithm and the input, so it lets you compare two methods fairly. The lab below counts comparisons for you while it sorts a row of bars. Try the same starting order with two different methods and watch the counters.

Inputs, outputs and the steps between

Before writing an algorithm, write down exactly what goes in and what must come out. For the greatest common divisor: the input is two positive whole numbers, and the output is one whole number that divides both, with no larger number doing the same. That description tells you how to test the result, and it often hints at the steps. It also reveals the edge cases: what if one number is 0? (The loop above returns the other number, which is the correct answer.) What if the two numbers are equal? Thinking about edge cases before running the code catches many mistakes.