Chapter 11The World of Algorithms

Let us add 4728 and 3695, following the five steps exactly as written.

• Step 1: Write one below the other, aligned from the right: 4728 over 3695.
• Step 2 (rightmost column): \(8 + 5 = 13\). This is 10 or more, so write the units digit, 3, and set carry = 1.
• Step 3 (next column left): \(2 + 9 + 1(\text{carry}) = 12\). This is 10 or more, so write 2, set carry = 1.
• Step 4 (repeat Step 3, next column): \(7 + 6 + 1 = 14\). Write 4, set carry = 1.
• Step 4 (repeat Step 3, next column — the leftmost digits): \(4 + 3 + 1 = 8\). This is less than 10, so write 8, set carry = 0.
• No more digits remain on the left, so Step 4's repetition stops.
• Step 5: The final carry is 0, so nothing more is written.

Reading the bottom row left to right gives 8423.

Try adding 42536 (5 digits) and 178 (3 digits). Written one below the other, aligned from the right:

  42536
  +  178

The rightmost 3 columns have a digit from both numbers, so Steps 2–3 work exactly as written: units \(6+8=14\) → write 4, carry 1; tens \(3+7+1=11\) → write 1, carry 1; hundreds \(5+1+1=7\) → write 7, carry 0.

But once we move further left, the 3-digit number has run out of digits — there is no digit of 178 in the thousands or ten-thousands column. The algorithm as literally written only says "add the two digits and the current value of carry" — it never says what to do when one number has no digit in that column.

In practice, we handle this by silently treating a missing digit as 0 (thousands: \(2+0+0=2\); ten-thousands: \(4+0+0=4\)), which gives the correct answer 42714. But this is an extra rule we are implicitly assuming, not one of the 5 steps as written.

In the Indian (and international) place-value system, a digit's position tells us its place value — units, tens, hundreds, and so on — counting from the rightmost digit. Aligning from the right guarantees that units sit under units, tens under tens, hundreds under hundreds, and so on, so that when we add a column we are always adding quantities of the same place value.

If we instead aligned from the left, digits of different place value would land in the same column — for instance, adding 47 and 138 by left-aligning would put the 4 (tens) of 47 under the 1 (hundreds) of 138, giving a meaningless sum.

In Step 3, we add two digits (each digit is between 0 and 9) together with a carry that is already either 0 or 1. The largest possible sum is therefore \(9 + 9 + 1 = 19\).

Since 19 is less than 20, dividing it by 10 gives a quotient of at most 1 — that is, the new carry (the number of complete tens generated) can only be 0 or 1, never 2 or more.

Step 5 only matters when the very last (leftmost) column produces a carry of 1 — that carry has nowhere left to go except a brand-new digit at the front of the answer.

Where it still works without Step 5: \(123 + 456\). Adding column by column: \(3+6=9\), \(2+5=7\), \(1+4=5\), and the final carry is 0. Since there is no leftover carry, skipping Step 5 makes no difference — the answer 579 is unaffected.

Where it fails without Step 5: \(999 + 1\). Units: \(9+1=10\) → write 0, carry 1. Tens: \(9+0+1=10\) → write 0, carry 1. Hundreds: \(9+0+1=10\) → write 0, carry 1. Without Step 5 to record this final carry, we would report the answer as just "000", i.e. 0 — instead of the correct answer, 1000.

(ii) is exactly the same idea with the two lists swapped:

Since both lists are already sorted in increasing order, an even more efficient version scans both lists together with two markers, one on each list, moving whichever marker points to the smaller current value forward — very similar in spirit to how we later combine the two divisor scans into one (section 11.3.1).

One direct approach mirrors the gcd algorithm exactly, but scans multiples instead of divisors:

A faster approach uses a gcd algorithm we already have: since \(m \times n = \gcd(m,n) \times \text{lcm}(m,n)\), we can compute

\[ \text{lcm}(m,n) = \dfrac{m \times n}{\gcd(m,n)} \]

This needs only one gcd computation (which we already know how to do efficiently) instead of generating and comparing two growing lists of multiples.

(i) Every divisor \(d\) of \(n\) pairs up with a partner divisor \(n/d\), and one of the two partners in each pair is always at most \(\sqrt{n}\) (they can only both equal \(\sqrt{n}\) when n is a perfect square). So instead of checking every number from 1 to n, we only need to check numbers from 1 up to \(\sqrt{n}\) — whenever we find that j divides n, we immediately know both j and \(n/j\) are divisors, without having to test \(n/j\) separately. For \(n = 18\), that means checking only up to \(\sqrt{18} \approx 4.24\), i.e. just \(j = 1, 2, 3, 4\), instead of all 18 numbers.

(ii) Not directly. Our gcd algorithm relied on each divisor list being built in strictly increasing order, so that the largest common divisor was simply the rightmost entry once we scanned it. But finding divisors in pairs produces them out of order — for instance for 18 we would find the pair (1, 18) first, then (2, 9), then (3, 6), giving something like [1, 18, 2, 9, 3, 6], which is not sorted. So "look at the rightmost element" would no longer reliably give the gcd; we would instead need to keep explicit track of the largest divisor seen so far (updating it whenever a new, larger one turns up in either half of a pair) rather than relying on the list's order.

What the algorithm computes would not change — the set of divisors found is exactly the same, since every number from 1 to n is still checked, just in the opposite order.

What would change is the order of the resulting list: scanning from n down to 1 produces the divisors in decreasing order instead of increasing order. This matters for the gcd algorithm, which relies on the list being in increasing order so that the largest common divisor is the rightmost entry. If the list is instead in decreasing order, the largest common divisor would be the leftmost entry (the first one found), not the rightmost.

This is actually a useful improvement. If we scan k from \(\min(m,n)\) down to 1 instead of from 2 up, the very first value of k we find that divides both m and n is automatically the largest such value — because we started checking from the biggest possible candidate and are working downward.

This means we do not need to scan all the way down to 1 at all: as soon as we find one common divisor, we can stop immediately and report it as the gcd, since nothing smaller that we haven't checked yet could possibly beat it. In the best case (for example, when \(\min(m,n)\) itself divides both numbers) this finds the gcd in a single check, though in the worst case (when the gcd is 1) it still has to scan all the way down to 1.

Using the division-based reduction \(\gcd(m,n) = \gcd(n, m \bmod n)\) throughout:

1789287 and 237656 share no common factor other than 1 — they are coprime.

Write \(m = qn + r\), where \(q\) is the quotient and \(r = m \bmod n\) is the remainder when m is divided by n, with \(0 \le r < n\).

Forward direction: suppose d divides both m and n. Since \(r = m - qn\), and d divides m and d divides n (so d also divides \(qn\)), d must divide the difference \(m - qn = r\). So d divides both n and r (= m mod n).

Reverse direction: suppose d divides both n and r. Since \(m = qn + r\), and d divides n (so d divides \(qn\)) and d divides r, d must divide the sum \(qn + r = m\). So d divides both m and n.

Since each direction holds, d divides m and n if and only if d divides n and m mod n — exactly the fact that justifies reducing \(\gcd(m,n)\) to \(\gcd(n, m \bmod n)\).

For example, divisors(7) = [1, 7], which has exactly 2 entries, so prime(7) reports true. But divisors(8) = [1, 2, 4, 8], which has 4 entries, so prime(8) reports false.

For example, divisors(18) = [1, 2, 3, 6, 9, 18]. Checking each: 1 is not prime (it has only one divisor), 2 is prime, 3 is prime, 6 is not prime, 9 is not prime, 18 is not prime. So primedivisors(18) = [2, 3].

(i) The prime factorisation of 180 can be represented as a list of (prime, exponent) pairs: \([(2,2), (3,2), (5,1)]\) — read as "2 raised to the power 2, times 3 raised to the power 2, times 5 raised to the power 1". This representation is compact and unambiguous, and it is easy to reconstruct 180 from it by multiplying out the pairs.

(ii) To compare two prime factorisations, we line them up by prime number rather than by position in the list — treating each factorisation as giving an exponent for every prime (using exponent 0 for a prime that doesn't appear at all). For instance, comparing 180 = \(2^2 \times 3^2 \times 5^1\) with 84 = \(2^2 \times 3^1 \times 7^1\), we compare exponent by exponent across the primes 2, 3, 5, 7: (2,1), (2,0), (1,1). This prime-by-prime comparison is exactly what is used to compute the gcd (take the smaller exponent of each shared prime, e.g. \(2^2 \times 3^1 = 12\)) or the lcm (take the larger exponent of every prime that appears in either number).