The World of Algorithms

Here are the steps exactly as the book gives them:

Example 1: 4738 + 2596. Write 4738 on top and 2596 below it, units under units (Step 1). Then:

Step 5: the carry is now 0, so nothing more is written. Reading the bottom row from left to right gives 7334, and \(4738 + 2596 = 7334\) is correct. So for these numbers, yes, the steps work.

Example 2: 3645 + 2465. Step 2 adds the rightmost digits:

Now read the two rules in Step 2 carefully. One is for a sum less than 10 and the other is for a sum more than 10. A sum of exactly 10 is neither, so the steps tell us nothing: we do not know what to write or what the carry should be. If we follow the steps precisely, we get stuck and cannot finish (the correct answer is 6110).

The same thing happens in Step 3 whenever two digits and the carry add up to exactly 10, for example \(4 + 5 + 1 = 10\).

Answer: we get the correct result only when no column adds up to exactly 10. To mend the algorithm, change “more than 10” to “10 or more” in both Step 2 and Step 3. With that change, 3645 + 2465 runs through to 6110.

Take 52817 + 694. Write 694 under the last three digits of 52817 (Step 1).

Now Step 4 says to repeat Step 3, because 52817 still has digits on the left. But Step 3 says “add the two digits and the carry”, and in the thousands column there is only one digit (2); the lower number has run out. The steps do not say what to do, so as written they do not handle this case.

The natural fix is to treat a missing digit as 0 (as if 694 were written 00694). With that change:

Step 5: the carry is 0. The bottom row reads 53511, and indeed \(52817 + 694 = 53511\).

So the steps work for numbers of different lengths only after we add one more instruction: “if one number has no digit in a column, use 0 for it”.

The value of a digit depends on its place. Aligning from the right puts units under units, tens under tens, hundreds under hundreds, so each column adds digits of the same place value, and a carry of 1 from one column is exactly one unit of the next place.

If we aligned from the left instead, two numbers of different lengths would line up wrongly. For 473 + 25:

Lined up from the left, the 2 of 25 sits under the 4 (hundreds) and the 5 under the 7 (tens), so 25 has been read as 2 hundreds and 5 tens, that is 250. Aligning from the right is what makes every column add like with like.

Each digit is at most 9. In Step 2 (the units) there is no carry yet, so the largest possible sum is

which is less than 20, so its tens digit is at most 1. The carry passed to the next column is therefore 0 or 1.

In Step 3 we add two digits and that carry. The largest possible sum is

again less than 20, so the new carry is again at most 1. Since the carry starts at 0 or 1 and every column passes on 0 or 1, the carry can never be more than 1, however long the numbers are.

Step 5 writes the last carry. Without it, a carry produced by the leftmost column is simply lost.

Works: 473 + 215.

The final carry is 0, so Step 5 would have done nothing anyway. Result 688, correct.

Fails: 473 + 695 (the book’s own example).

The bottom row reads 168 and the final carry of 1 is never written. The answer comes out as 168 instead of 1168.

Rule: without Step 5 the algorithm is correct exactly when the leftmost column adds up to less than 10 (no carry out of it), and wrong whenever the answer has one more digit than the longer number.

(i) This is the gcd algorithm’s “common divisors” step turned round: instead of keeping the elements that do appear in the other list, we keep the ones that do not.

Trace with List 1 = divisors(375) = [1, 3, 5, 15, 25, 75, 125, 375] and List 2 = divisors(825) = [1, 3, 5, 11, 15, 25, 33, 55, 75, 165, 275, 825]:

Result: [125, 375].

Because both lists are in increasing order, we need not search the whole of List 2 for every x. We can walk through both lists together, once, as when merging two sorted lists:

The simple version checks every x against every y; the faster one looks at each element of each list only once. Both give the same list, and the result is again in increasing order.

(ii) Exactly the same algorithm with the roles of the lists swapped: for each number y in List 2, if y does not appear in List 1, add y to only-in-2. For the lists above this gives [11, 33, 55, 165, 275, 825].

The lcm is the smallest number that both m and n divide. Every common multiple is a multiple of the larger number, so we only need to test the multiples of the larger number, in increasing order, and stop at the first one that the smaller number divides.

It always stops by \(j = n\) at the latest, because \(m \times n\) is a common multiple of m and n.

Trace for lcm(375, 825): the larger number is 825.

So lcm(375, 825) = 4125, found after checking 5 multiples.

A faster way, using gcd. For any two numbers,

With gcd(375, 825) = 75 from the chapter, keep the product unevaluated and cancel first:

This version needs only a gcd (which Euclid’s algorithm finds quickly), one multiplication and one division.

(i) If \(j\) divides \(n\), then so does \(n \div j\), and the two form a pair \(j \times (n \div j) = n\). In every pair the smaller number is at most \(\sqrt n\): if both were bigger than \(\sqrt n\), their product would be bigger than \(n\). So it is enough to examine \(j = 1, 2, 3, \ldots\) only while \(j \times j \le n\), and for each \(j\) that divides \(n\), write down the pair \((j,\ n \div j)\).

Trace for n = 18:

(4 does not divide 18, so it gives no pair.) Only 4 numbers were examined instead of 18. In general we examine about \(\sqrt n\) numbers, the whole numbers from 1 up to \(\sqrt n\). For a 6-digit number like 810000 that is 900 checks instead of 810000.

(ii) Not exactly as described. Listed pair by pair, the divisors are not in increasing order, e.g. divisors(18) becomes [1, 18, 2, 9, 3, 6]. Our gcd algorithm reported the rightmost element of the list of common divisors, which is the largest only because the lists were in increasing order.

Try gcd(12, 18) with pair-order lists: divisors(12) = [1, 12, 2, 6, 3, 4] and divisors(18) = [1, 18, 2, 9, 3, 6]. Checking each element of the first list against the second gives common divisors [1, 2, 6, 3]. The rightmost element is 3, but gcd(12, 18) = 6. The algorithm gives a wrong answer.

To repair it, change the last step to “report the largest element of the list of common divisors” (or sort the lists into increasing order first). With that change the pair method works, and is much faster.

Scanning from \(n\) down to 1, each divisor found is added at the end of the list, so the list comes out in decreasing order. For example, divisors(18) becomes [18, 9, 6, 3, 2, 1].

The list of common divisors is built by going through the first list in order, so it is decreasing too. For gcd(375, 825) it becomes

If Step 5 is left unchanged (“report the rightmost element”), the algorithm reports 1, the smallest common divisor, which is wrong. The change needed is in Step 5:

Now gcd(375, 825) = 75, correct. (Better still, since the first common divisor we meet is now the largest, we can stop as soon as we find it.)

Going downwards, the first common divisor we meet is the largest one, so it is the gcd. We no longer need most-recent-common-divisor to be updated again and again; we stop at the first hit:

It always stops, at worst at \(k = 1\), because 1 divides every number.

m = 6, n = 12: min = 6. \(k = 6\) divides both 6 and 12, so gcd(6, 12) = 6 after 1 check (the forward scan in the book needed 5 checks, from 2 to 6).

m = 375, n = 825: min = 375. \(k = 375\) does not divide 825, nor does 374, 373, …; the first k that divides both is 75. The checks run from 375 down to 75:

so gcd(375, 825) = 75.

Careful: if we kept the old rule (keep scanning to the end and update most-recent-common-divisor every time), the last update would be at \(k = 1\) and the answer would wrongly come out as 1. Working backwards only helps if we stop at the first common divisor.

In the worst case (gcd = 1) we still check every number from min(m, n) down to 1, so the effort still grows with the size of the numbers.

Here \(m \bmod n\) is the remainder when m is divided by n, so each reduction is one long division.

(i) gcd(375, 825)

Step 1: \(375 < 825\), so reverse and compute gcd(825, 375). Each row divides the first number by the second; the remainder becomes the new second number.

The remainder is now 0, so Step 2 gives gcd(375, 825) = 75, after 2 reductions. (The subtraction version in the book needed 7 reductions for the same pair.)

(ii) gcd(51000, 81000)

Step 1: \(51\,000 < 81\,000\), so reverse and compute gcd(81 000, 51 000). Each row divides the first number by the second; the remainder becomes the new second number.

The remainder is now 0, so Step 2 gives gcd(51 000, 81 000) = 3000, after 5 reductions.

(iii) gcd(1789287, 237656)

Each row divides the first number by the second; the remainder becomes the new second number.

The remainder is now 0, so Step 2 gives gcd(1 789 287, 237 656) = 1, after 13 reductions. The two numbers have no common divisor other than 1; they are co-prime.

(iv) gcd(2587392, 157656)

Each row divides the first number by the second; the remainder becomes the new second number.

The remainder is now 0, so Step 2 gives gcd(2 587 392, 157 656) = 24, after 7 reductions.

Divide m by n. If the quotient is q and the remainder is r, then \(r = m \bmod n\) and

(1) If d divides m and n, then d divides n and r. Write \(m = a \times d\) and \(n = b \times d\) for whole numbers a and b. Then

so d divides r. And d divides n is given.

(2) If d divides n and r, then d divides m and n. Write \(n = b \times d\) and \(r = c \times d\). Then

so d divides m. And d divides n is given.

Both directions hold, so the common divisors of m and n are exactly the common divisors of n and \(m \bmod n\). In particular the greatest of them are equal: \(\gcd(m, n) = \gcd(n,\ m \bmod n)\), which is why the improved Euclid algorithm is correct.

Example. m = 825, n = 375: \(825 = 2 \times 375 + 75\), so \(m \bmod n = 75\). The common divisors of 825 and 375 are 1, 3, 5, 15, 25, 75, and the common divisors of 375 and 75 are also 1, 3, 5, 15, 25, 75. A number such as 11 divides 825 but not 375, and it does not divide 75 either.

This works because the list divisors(n) always contains 1 and n. It has exactly two elements precisely when there is nothing else, which is the definition of a prime.

Note that n = 1 is correctly reported as not prime: its list has only one element.

The algorithm uses prime(d) from Q3 as a basic step. Since divisors(n) is in increasing order, the list of prime divisors is too.

Trace for n = 60: divisors(60) = [1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60].

So primedivisors(60) = [2, 3, 5], and indeed \(60 = 2^2 \times 3 \times 5\).

Algorithm. Use primedivisors(n) from Q4, then find how many times each prime goes into n by dividing repeatedly.

Trace for n = 180: primedivisors(180) = [2, 3, 5].

(i) Represent the factorisation as a list of pairs (prime, exponent), with the primes in increasing order:

Each pair (p, e) stands for \(p^e\), and the number is the product of all of them: \(2^2 \times 3^2 \times 5^1 = 180\). Primes that do not divide the number are simply left out.

(ii) To compare two factorisations, go through the primes. A prime that appears in both lists divides both numbers; the highest power of it dividing both is the smaller of the two exponents. So:

Example: gcd(180, 825). \(825 = 3 \times 5^2 \times 11\), i.e. [(3, 1), (5, 2), (11, 1)]. The common primes are 3 and 5:

Since both lists are in increasing order of primes, they can be compared in a single pass, like the merge in Exercise Set 11.2, Q1. Taking the larger exponent of every prime in either list gives the lcm instead: