Chapter 11 — The World of Algorithms

A small child adds 5 and 7 by drawing 5 dots, then 7 more dots, and counting all of them: 12. That works, but try it for 5834 + 4729. You would have to draw and count more than ten thousand dots! Long ago people found a much better way, and you use it every day without thinking about it.

The column method. Write the numbers one below the other so that the units are lined up, then the tens, then the hundreds, and so on. Add each column from right to left, and whenever a column total reaches 10 or more, write its units digit and carry 1 to the next column.

An algorithm is a step-by-step procedure that solves every problem of a certain kind, with steps so precise that anyone (or any machine) following them exactly gets the right answer. Here is the column method written as an algorithm.

• Step 1. Write the two numbers one below the other, lining up the digits from the right.
• Step 2. Set carry = 0. Start with the rightmost column.
• Step 3. Add the two digits of the column (a missing digit counts as 0) and the carry. If the total is less than 10, write it below and set carry = 0. If it is 10 or more, write its units digit below and set carry = 1.
• Step 4. If there is a column further to the left, move to it and repeat Step 3.
• Step 5. When no columns are left, if carry = 1, write 1 at the far left of the answer.

Basic steps. Every algorithm is built on a few actions we assume we can already do. Here the basic step is adding two single digits and a carry, a fact we know by heart. The algorithm then tells us in what order to use the basic step.

Every step matters. Suppose we forget Step 5. Then 58 + 47 gives: units 8 + 7 = 15, write 5, carry 1; tens 5 + 4 + 1 = 10, write 0, carry 1; stop. The answer written is 05, instead of 105. The algorithm works for 23 + 14 but fails whenever the leftmost column produces a carry. A good algorithm must handle every case, including numbers with different numbers of digits (that is why a missing digit counts as 0).

Why is it so much faster? Suppose we count one dot each second, and add one column (with a carry) in 15 seconds.

Each extra digit multiplies the counting work by about 10, but adds only one more column to the algorithm. The work of the column method grows with the number of digits, not with the size of the numbers. This idea, comparing how the work grows, will guide the whole chapter.

Giving a list of steps is only half the job. We must also justify that the steps always give the right answer. Addition is defined by joining the two collections and counting everything. Why should adding digits column by column give the same result?

Grouping by place value. In our number system, 583 means 5 hundreds, 8 tens and 3 units, and 472 means 4 hundreds, 7 tens and 2 units. Joining the two collections, we can join the units with the units, the tens with the tens, and the hundreds with the hundreds, because the order in which we put things together does not change the total. So

We get 9 hundreds, 15 tens and 5 units. But 15 tens is not a single digit. Ten tens make one hundred, so we exchange 10 of the tens for 1 hundred. Now we have 10 hundreds, 5 tens and 5 units. Ten hundreds make one thousand, so we exchange again: 1 thousand, 0 hundreds, 5 tens, 5 units, which is 1055. Each exchange is exactly what the algorithm calls a carry.

The justification in one sentence. The algorithm adds each place-value group separately and, whenever a group reaches ten, turns those ten into one item of the next larger group; since nothing is lost or created, the result is the true total.

Why line up from the right? The rightmost digit of every whole number is its units digit. Lining up from the right puts units under units and tens under tens, so we only ever join groups of the same size. Lining up from the left would add, for example, the hundreds of one number to the tens of another.

Extending the algorithm. Once you see why it works, you can change it for new situations with confidence. To add decimals such as 3.75 + 12.6, line up the decimal points (so that tenths are under tenths), fill a missing place with 0 (12.60), and add from the right exactly as before: 3.75 + 12.60 = 16.35. The reason is the same: groups of ten hundredths make a tenth, ten tenths make a unit.

Correctness and efficiency. From now on we will ask two questions about every algorithm:

• Correctness: does it always give the right answer? We answer with a justification.
• Efficiency: how much work does it take, and how does the work grow as the inputs grow?

A method that is fast but sometimes wrong is useless. A method that is correct but takes years for large numbers is not practical. Good algorithms are both correct and efficient.

To find the greatest common divisor (gcd), also called the highest common factor (HCF), of two numbers, we can break the problem into smaller pieces. First find all divisors of each number, then compare the two collections. Breaking a problem into simpler sub-problems is the first habit of algorithm design.

Sub-problem: list the divisors of n. Every divisor of n lies between 1 and n. The most direct method is to test each of these numbers in turn. We keep the divisors we find in a list, written in square brackets, such as [1, 2, 5]. At the start we know none, so the list is empty, [ ].

• Step 1. Start with an empty list, called list-of-divisors.
• Step 2. For each number j = 1, 2, 3, …, n: if j divides n exactly, add j at the end of list-of-divisors.
• Step 3. When j has reached n, report list-of-divisors.

Names for changing values. The names j and list-of-divisors let us talk about values that change as the algorithm runs. Without them, the steps would be clumsy to write.

Executing the algorithm. Running the steps by hand is called executing or tracing the algorithm. Here is a trace for n = 20.

Because we tested j in increasing order, the list comes out in increasing order. This will be useful in the next step. The basic step assumed is: we can decide whether one number divides another.

How much work? For n = 20 we made 20 tests; for n = 375 we would make 375; for n = 81000, eighty-one thousand. The work grows with the size of n itself, just like counting dots.

A first improvement: pairs. Divisors come in pairs whose product is n: for 20 the pairs are (1, 20), (2, 10), (4, 5). In each pair the smaller number is at most the square root of n, because if both were larger, their product would be larger than n. So it is enough to test j from 1 up to √n and record each divisor with its partner n ÷ j. For n = 20 that is only j = 1, 2, 3, 4 (since 4 × 4 = 16 is not more than 20 but 5 × 5 = 25 is). For n = 10000 it is 100 tests instead of 10000. The list then needs sorting if we want it in order.

Now we can put the pieces together. The greatest common divisor of two numbers m and n, written gcd(m, n), is the largest number that divides both. To compute it straight from this definition:

• Step 1. Let divisors-of-m = divisors(m).
• Step 2. Let divisors-of-n = divisors(n).
• Step 3. Start with an empty list, common-divisors.
• Step 4. For each number x in divisors-of-m: if x also appears in divisors-of-n, add x to common-divisors.
• Step 5. Report the last (rightmost) entry of common-divisors as gcd(m, n).

Example: gcd(84, 120).

Going through the divisors of 84 one by one: 1, 2, 3, 4, 6 are in the second list; 7 is not; 12 is; 14, 21, 28, 42 and 84 are not. The common list is [1, 2, 3, 4, 6, 12], and its last entry gives gcd(84, 120) = 12.

Why is the last entry the greatest? Step 4 goes through divisors-of-m in increasing order, so common-divisors is built in increasing order too. Its last entry is therefore its largest. And common-divisors is never empty, because 1 divides every number.

Why is this algorithm correct? It follows the definition word for word: list every divisor of each number, keep those common to both, take the largest. Nothing is skipped, so the answer must be the gcd.

Data structures. While the algorithm runs, it keeps intermediate results: three lists of numbers. A way of organising such information is called a data structure. A list is the simplest one. Here it matters that the lists are sorted: because they are in increasing order, we know the answer is at the right end, and we could also stop early when comparing. Choosing a good data structure often makes an algorithm faster; you will meet many more in higher classes.

Related problems. With small changes the same plan solves other problems.

• Elements of List 1 that are not in List 2: go through List 1 and keep each x that does not appear in List 2.
• Least common multiple: lcm(m, n) is the smallest number that both divide. One method: check m, 2m, 3m, … and stop at the first one that n divides. For 84 and 120: 84, 168, …, 840; the first multiple of 84 divisible by 120 is 840 = 10 × 84 = 7 × 120.
• Shortcut: lcm(m, n) × gcd(m, n) = m × n, so lcm(84, 120) = 84 × 120 ÷ 12 = 840.

The cost. For gcd(84, 120) we tested 84 + 120 = 204 candidate divisors and then compared lists. For 54000 and 81000 each list has 80 entries and we would test 135000 candidates. The method is correct but slow. In the next topics we make it faster.

A correct algorithm is a good start. The next question is: can it do less work and still be correct? Let us refine the gcd algorithm in small steps, checking each time that the answer does not change.

Refinement 1: one scan instead of two. The first algorithm tests 1 to m for divisors of m and then starts again, testing 1 to n for divisors of n: m + n tests. Instead, run j once from 1 to the larger of the two numbers, written max(m, n). For each j, if j divides m, add it to the first list; if j divides n, add it to the second. Now there are only max(m, n) tests.

Refinement 2: collect common divisors directly. In the same scan, simply ask: does j divide both m and n? If yes, add j to common-divisors. There is no need for separate lists.

Refinement 3: stop at the smaller number. A common divisor cannot be larger than the smaller of the two numbers, min(m, n). So the scan need only run from 1 to min(m, n).

Refinement 4: drop the list. Each time we find a larger common divisor, all the earlier ones become useless. So keep only one number, called most-recent-common-divisor. Start it at 1 (since 1 always divides both). For each k from 2 to min(m, n): if k divides both m and n, set most-recent-common-divisor = k. When the scan ends, it holds the gcd.

So gcd(18, 24) = 6. The table is a trace of the refined algorithm.

Refinement 5: scan backwards. If we test k = min(m, n), min(m, n) − 1, …, down to 1, the first common divisor we meet is the greatest, and we can stop at once. For gcd(84, 120) we test 84, 83, …, 12 and stop: 73 tests, compared with 204 for the first algorithm. But when the gcd is 1 we still test every number down to 1.

Comparing the versions for gcd(84, 120).

Correctness is kept. Each refinement changes how the work is organised, not what is computed, so every version still returns the gcd.

The limit of this approach. All these versions may still need to test every number up to min(m, n). If the smaller number grows from 3 digits to 5 digits, the work grows about 100 times. To do better we need a new idea, not just tidier bookkeeping. That idea is Euclid’s.

More than 2300 years ago Euclid wrote down, in his Elements, a completely different way to find the gcd. Instead of searching through divisors, it keeps replacing the problem with a smaller problem that has the same answer. (Historians think earlier Greek mathematicians already knew it; Euclid is the first to record it.)

The key fact. If m ≥ n, then gcd(m, n) = gcd(n, m − n).

Why? We show that m, n and n, m − n have exactly the same common divisors.

• If d divides m and n, write m = ad and n = bd. Then m − n = ad − bd = (a − b)d, so d also divides m − n.
• If d divides n and m − n, write n = xd and m − n = yd. Then m = n + (m − n) = (x + y)d, so d also divides m.

The two collections of common divisors are identical, so their largest members are equal. Think of it with tiles: if strips of length m and n can both be covered exactly by tiles of length d, then so can the leftover piece m − n, and the other way round.

When to stop. gcd(m, m) = m, and the next reduction gives gcd(m, 0). Every number divides 0, so gcd(m, 0) = m. That is the stopping rule.

Euclid’s algorithm for gcd(m, n)

• Step 1. If m is smaller than n, swap them and compute gcd(n, m).
• Step 2. If n = 0, report m as the answer.
• Step 3. Otherwise replace the problem by gcd(n, m − n) and go back to Step 1.

Trace for gcd(84, 36).

Five subtractions found the answer, with no list of divisors at all.

Does it always stop? Each subtraction makes the larger number smaller, while all numbers stay whole and not negative. A whole number cannot keep decreasing for ever, so eventually one number becomes 0.

The weak spot. Try gcd(101, 2). The algorithm subtracts 2 again and again: gcd(99, 2), gcd(97, 2), …, gcd(3, 2), gcd(2, 1), gcd(1, 1), gcd(1, 0). That is 52 reductions. In general gcd(2k + 1, 2) needs about k steps, so the work still grows with the size of the number. Repeated subtraction of the same number is really a slow way of dividing, and that suggests the improvement in the next topic.

When 101 has 2 subtracted from it again and again until less than 2 remains, what remains is 1, which is exactly the remainder when 101 is divided by 2. One division does the work of fifty subtractions. Indian mathematicians, at least from the time of Āryabhaṭa (Āryabhaṭīya, 499 CE), used this ‘long division’ procedure with place-value numerals to find the greatest common divisor.

Notation. m mod n means the remainder when m is divided by n. For example, 17 mod 5 = 2, 33 mod 7 = 5 and 1071 mod 462 = 147 (since 1071 = 2 × 462 + 147).

The improved rule. If m ≥ n and n is not 0, then gcd(m, n) = gcd(n, m mod n). The reason is the same as before. Write m = qn + r with r = m mod n. Any d that divides m and n divides m − qn = r; any d that divides n and r divides qn + r = m. So the common divisors do not change.

• Step 1. If m is smaller than n, swap them.
• Step 2. If n = 0, report m as the answer.
• Step 3. Otherwise replace the problem by gcd(n, m mod n) and go back to Step 1.

Only Step 3 has changed. After the first step, the remainder is always smaller than the divisor, so Step 1 never needs to swap again.

Example: gcd(1071, 462).

So gcd(1071, 462) = 21 after three divisions. The subtraction version would need 12 reductions. For gcd(101, 2): 101 mod 2 = 1, giving gcd(2, 1); 2 mod 1 = 0, giving gcd(1, 0) = 1. Two steps instead of 52.

The long-division layout. Each remainder becomes the next divisor, and the previous divisor becomes the next dividend. Written as a ladder of divisions, the last non-zero remainder (or the last divisor, when the remainder becomes 0) is the gcd. This is the method taught in Indian texts and still used in schools today.

How efficient is it? It can be shown that the number of division steps grows only with the number of digits of the numbers, as in column addition, and not with their size. (The proof is for higher classes.) Even numbers with many digits, such as gcd(2587392, 157656) = 24, take only 7 divisions.

Looking back over the chapter, every algorithm we wrote was made from a few kinds of instruction:

• Basic steps that we assume we can do directly: adding two digits, testing whether j divides n.
• Repetition: doing the same step for each item, as in ‘for each j = 1, 2, …, n’, or ‘go back to Step 1’.
• Conditions: doing a step only when something is true, as in ‘if j divides n, add j to the list’.
• Named values that change as we go, such as carry, j and most-recent-common-divisor, and data structures such as lists.

A design checklist. When you write an algorithm for a new problem:

• Step 1. Understand exactly what is given and what must be produced.
• Step 2. Break the problem into smaller problems you already know how to solve.
• Step 3. Write precise steps, using names for values that change.
• Step 4. Trace the steps on small examples, including awkward cases (0, 1, equal numbers, different lengths).
• Step 5. Justify why the steps are always correct.
• Step 6. Count the work and ask how it grows; then look for a better idea.

Example: is n prime? A prime has exactly two divisors, 1 and itself. So: compute divisors(n); if the list has exactly 2 entries, report ‘prime’, otherwise ‘not prime’. This is correct (and handles n = 1, whose list [1] has one entry, so 1 is not prime). A faster version tests only j = 2, 3, … up to √n and stops at the first divisor found. For 221 it finds 13 (221 = 13 × 17) after 12 tests.

Example: prime divisors of n. Compute divisors(n), then keep only those entries d for which ‘is d prime?’ says yes. For 60: divisors [1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60] give prime divisors [2, 3, 5]. One algorithm is used as a basic step inside another.

A pinch of history. Around 820 CE the Persian scholar Muḥammad ibn Mūsā al-Khwārizmī, working at the House of Wisdom in Baghdad, wrote a book explaining the Indian place-value numerals and the Indian methods for addition, subtraction, multiplication and division. Its Arabic original is lost, but a Latin translation from the 12th century, known as Algoritmi de numero Indorum (‘al-Khwārizmī on the Indian numbers’), spread these methods across Europe. ‘Algoritmi’, the Latin form of his name, gave the word algorism for these Indian ways of calculating, and later algorithm, which now means any precise step-by-step procedure.

Algorithms today. A computer program is an algorithm written in a language a machine can follow. Maps that find the shortest route, apps that sort your photos and the methods that keep online payments secure (which use gcd calculations with very large numbers) all depend on algorithms that are correct and efficient, exactly the two questions of this chapter.