The World of Algorithms: Class 9 Ganita Manjari · Chapter 11

Ask a map app for the quickest way to the railway station and it suggests a route within a second. A music app picks the next song, and a shopping site guesses what you might buy. People shrug and say, “the algorithm decided”. So what is this thing called an algorithm, and where does mathematics come into it?

Think about how tea is made at home. Boil water, add tea leaves, then milk, then sugar “to taste”. That is a list of steps, but “to taste” leaves the cook to decide. A mathematical procedure leaves nothing to taste. Every step says exactly what to do, so anyone who follows it reaches the same answer. In this chapter we study two such procedures closely: adding numbers and finding a greatest common divisor. For each one we ask three questions. What are the exact steps? Why do they give the right answer? How much work do they take?

11.1 Adding Numbers

Suppose nobody had ever shown you column addition, and someone asked for 586 + 749. You could draw 586 dots, draw 749 more, and count the whole crowd: all 1335 of them. That is really how small children add 6 + 8, by counting everything. The method never fails, but for big numbers it would take ages.

You already know a far better way, and Fig. 11.1 puts it next to counting for a small sum. On the left, every dot has to be counted. On the right, the numbers are stacked by place value, and two single-digit sums finish the job. When a column reaches 10 or more, a carry is handed to the next column.

11.1.1 Adding Numbers Digit by Digit

Column addition deserves a name of its own: it is an algorithm (कलन-विधि). What makes it one is not cleverness but two other qualities. It is general: the same instructions handle 23 + 14 and 586 + 749 alike. And it is exact: no instruction needs judgement or taste.

Let us write the instructions down so carefully that someone who has never met column addition, or a machine, could follow them. We call the result ADD. The word carry names a number that we keep track of while we work; you will soon see why it is always 0 or 1.

When we follow ADD's steps for two particular numbers, we are said to execute (or run) it. Fig. 11.2 executes ADD on 586 + 749. Step 2 handles one column at a time, and Step 3 keeps sending us one column to the left until none are left.

ADD never says how to work out 8 + 7. It simply trusts you to know single-digit sums by heart, the way a recipe trusts you to know how to boil water. Actions that an algorithm uses without spelling them out are its basic steps. For ADD, one column is a basic step: add two digits and a carry, write a digit, update the carry. Any algorithm has to stop explaining somewhere, and its basic steps mark that point.

Why the column method is so much faster

Both methods give the same answer, so the real question is how much work each one costs. Add one digit to each number and the numbers become roughly ten times larger, and so does the pile of dots. ADD just gains a single extra column.

Let us put rough times on this. Suppose you can count 2 dots a second, and you spend a careful 10 seconds on each column of ADD. Table 11.1 compares the two methods as the numbers grow.

Read the table down its columns. The counting times explode, from under a minute to half a day, while the times for ADD creep up by 10 seconds a row. This is the whole point of a good algorithm: its work stays modest even when the numbers get large. From now on we judge every algorithm the same way, by asking how its work grows as its input grows.

Why the column method gives the right answer

Speed is worthless if the answer is wrong, so we also owe a reason why ADD always agrees with counting. Picture 47 as 4 rods of ten cubes plus 7 loose cubes, and 38 as 3 rods plus 8 loose cubes, as in Fig. 11.3. Tipping everything into one heap and counting it gives the true total; that is what 47 + 38 means. ADD reaches the same total by counting loose cubes first and rods afterwards.

Seven loose cubes and eight loose cubes make fifteen: enough to snap ten of them into a new rod, with five left loose. Snapping that rod together is exactly what the carry records. A hundred is a bundle of ten rods, so the same snapping-together can happen one column further left. Grouping cubes never adds or removes a cube, so the rods and loose cubes we end with count exactly the cubes we started with.

11.2 Greatest Common Divisor

Now a second familiar problem. A tailor has two ribbons, 84 cm and 126 cm long. She wants to cut both into pieces of one equal length with nothing left over. What is the longest piece she can cut? The length must divide 84 and divide 126, and we want the largest such number. It is the greatest common divisor of 84 and 126, written $\gcd (84,126)$. You may know it as the highest common factor, or HCF (महत्तम समापवर्तक).

You could find this with prime factorisation, as in earlier classes. Instead, let us pretend we know nothing except what the words greatest common divisor say, and build an algorithm straight from them. Read the name from the back. Divisor: find the numbers that divide. Common: keep the ones shared by both numbers. Greatest: choose the largest. For two numbers $m$ and $n$ that gives a three-part plan.

1. Find all the divisors of $m$ and write them down.
2. Find all the divisors of $n$ and write them down.
3. Compare the two collections and pick out the largest number that appears in both.

Each part is a smaller job than the whole problem, and smaller jobs are easier to turn into exact steps. We take them one at a time.

11.2.1 Computing the Divisors of a Number

A divisor (भाजक) of $n$ is a whole number that divides $n$ with remainder 0. Finding all of them is like taking a roll call. Call out 1, 2, 3, and so on up to $n$, and every number that divides $n$ exactly answers “present”. Nobody beyond $n$ can answer, because a divisor of $n$ is never larger than $n$.

The answers must be written down somewhere. We use a list: an ordered row of values inside square brackets, such as $[2,5,9]$. Before the roll call starts, nobody has answered, so the list begins empty, written $[]$. Each new answer is appended, that is, written at the end.

Try reading Step 2 aloud without the letter $j$: “for each number from 1 to $n$, if that number divides $n$, append that number…”. It soon gets muddled. Short labels such as $j$ and found keep the steps crisp. A label for a value that changes while an algorithm runs is called a variable. Step 2 also shows two new features: a step can be repeated (once for each $j$), and it can be conditional (append $j$ only if it divides $n$).

The finished list $[1,2,4,5,10,20]$ comes out in increasing order. That is no accident: the roll call runs upwards, so each divisor joins the list after every smaller one. Keep this fact in mind, because we use it soon. Here the basic step is a divisibility test, which we treat as something we can always do, for instance by long division.

11.2.2 Finding the Greatest Common Divisor

Two lists are on the table. Which number is in both, and biggest? For 36 and 60 the answer, 12, almost jumps out, as Fig. 11.5 shows. For 1680 and 2520, which have 40 and 48 divisors, nothing jumps out, and a tired eye easily skips a match. (Their gcd is 840; a much faster method later in the chapter finds it in two divisions.)

So we hand the comparison to one more small algorithm. Picture a shopkeeper checking a delivery: she reads down her order list and ticks each item that also appears on the delivery note. In the same way, we read the first divisor list from left to right and copy every entry that also appears in the second list into a new list, common. Since 1 divides everything, common always gets at least one entry.

Now a pleasant surprise. Both divisor lists were sorted, and we read the first one from left to right, so common is sorted too. Its biggest entry sits at the right-hand end. The gcd is therefore simply the last entry of common, and no further search is needed.

11.2.3 First Algorithm for gcd

Snap the three parts together and we have a complete gcd algorithm. Notice that it does not repeat the instructions of DIVISORS. It simply calls on DIVISORS twice, the way a biryani recipe might say “cook the rice” without explaining how. Reusing a trusted algorithm inside a bigger one is one of the most useful habits in mathematics and computing.

11.3 Data Structures

Think of the ticket checker on a long-distance train. Her reservation chart is printed coach by coach and berth by berth, so she can find any passenger in seconds. If the names were printed in the order the tickets were booked, the same information would cost her far more effort. How information is arranged decides how quickly we can use it.

Algorithms face the same issue. GCD-LIST keeps working values that are not the answer itself: the lists A, B and common. Each is a whole collection of numbers, held in increasing order. Any such arrangement of working values is called a data structure, and the sorted list is one of the simplest. Its sortedness paid off at the end, when the gcd could be read straight from the right-hand end of common.

Giving each working value a short name, as we did with A, B and common, keeps the steps readable. Your phone's contact list is another data structure you use daily: sorted by name, it lets you find a friend without reading every entry. Higher classes study many more.

11.3.1 Improving the Algorithm

GCD-LIST is correct, but wasteful. A good habit is to look at an algorithm and ask: which work could never change the answer? Each time we spot such waste we can remove it. Table 11.2 records four rounds of trimming for $m=36$ and $n=60$. It scores each version by the candidates it looks at and the values it keeps in memory.

The last change deserves a closer look. The scan climbs upwards, so every common divisor it meets is bigger than all the ones before, and the older ones are dead weight. One variable, best, is enough. It begins at 1, which divides every number, and is overwritten whenever a bigger common divisor turns up. Fig. 11.6 shows the shrinking work as bars.

11.3.2 Analysing these Algorithms

We now have five versions of one algorithm. Are they all right, and are any of them fast? These are the two questions to ask about every algorithm.

Correctness. Think of the versions as links in a chain. The first link, GCD-LIST, can be trusted because it is the definition of the gcd turned into steps. Each later link differs from the one before only by throwing away work that could not affect the result: candidates too large to divide both numbers, or lists that were never read again. A chain of such links does not break, so GCD-SCAN at the end is as correct as GCD-LIST at the start.

Efficiency. Speed is another matter. GCD-SCAN still visits every candidate up to the smaller number. Hand it a pair of 9-digit numbers and it may look at hundreds of millions of candidates; a computer copes, but a person with pencil and paper never would. In the language of Table 11.1, GCD-SCAN behaves like counting dots, not like ADD. That raises a challenge: is there a gcd algorithm whose work follows the length of the numbers rather than their size?

11.3.3 Euclid’s Subtraction Algorithm

The answer is more than 2300 years old. Around 300 BCE, Euclid of Alexandria gathered the mathematics of his time into the Elements, a work studied for over two thousand years. This method appears near the start of its Book VII. It was probably not his own invention, since earlier Greek mathematicians seem to have used it, but his account is the one that has come down to us.

Making the problem smaller

Try a small experiment first. The common divisors of 30 and 18 are 1, 2, 3 and 6. Now replace 30 by $30-18=12$: the common divisors of 18 and 12 are again 1, 2, 3 and 6. Nothing was lost and nothing was gained, yet the numbers got smaller. Euclid's idea is that this always happens.

Fig. 11.7 shows the idea on a number line. A hop length that lands exactly on $n$ and on $m$ also covers the stretch between them, of length $m-n$, in whole hops. Euclid himself reasoned with lengths in much this way.

Each subtraction makes the total $m+n$ smaller, so the process cannot go on for ever: sooner or later the smaller number hits 0. What is $\gcd (m,0)$? Every whole number $d$ divides 0, because $0=0\times d$. So the common divisors of $m$ and 0 are just the divisors of $m$, and the greatest of these is $m$ itself. Hence $\gcd (m,0)=m$: when a 0 appears, the other number is the answer. For example, $(9,9)$ becomes $(9,0)$, and the answer is 9.

There is a neat picture of EUCLID-SUB. Draw an $m$ by $n$ rectangle. Each subtraction cuts an $n$ by $n$ square off the end, leaving a smaller rectangle whose sides are the new pair. When a cut leaves nothing over, the side of the last square is the gcd. Fig. 11.8 does this for a 42 by 24 rectangle.

EUCLID-SUB is a big step forward, but give it one large number and one small one and it crawls. For $\gcd (1000,3)$ it chips away 3 at a time: $(1000,3)$, $(997,3)$, $(994,3)$, … all the way down to $(3,1)$, and then needs three more steps. That is 336 subtractions. A 7-digit number paired with 3 would need over a million. The work still follows the size of the numbers, not their length.

11.3.4 Āryabhaṭa’s Division Algorithm

Look again at $\gcd (1000,3)$. Taking 3 away from 1000 again and again, 333 times, leaves 1. One division does exactly that in a single stroke: $1000=333\times 3+1$. The leftover 1 is the remainder.

Indian mathematicians worked in exactly this way. In the Āryabhaṭīya, completed in 499 CE, Āryabhaṭa describes a method, now known as kuṭṭaka (“the pulveriser”), for solving certain equations in whole numbers. Its first stage divides two numbers into each other again and again, each time keeping only the remainder. That repeated division is precisely what finds a gcd, and with Indian place-value numerals it became a compact long-division method.

That suggests a one-line upgrade to EUCLID-SUB. Wherever it would subtract $n$ from $m$ over and over, let it divide once and keep the remainder, so that the pair $(m,n)$ jumps straight to $(n,m<mrow><mi\; mathvariant="normal">m</mi><mi\; mathvariant="normal">o</mi><mi\; mathvariant="normal">d</mi></mrow>n)$. The theorem below shows that the jump keeps the gcd the same.

Step 1 now matters only at the very start, because a remainder is always smaller than the divisor. Run the slow case again: $\gcd (1000,3)$ becomes $\gcd (3,1)$, then $\gcd (1,0)$, and the answer 1 arrives after 2 divisions instead of 336 subtractions. In fact $\gcd (m,3)$ never needs more than 3 divisions, however large $m$ is.

The long-division layout

By hand, EUCLID-DIV is a chain of divisions. Each divisor becomes the next number to be divided, and each remainder becomes the next divisor. The chain stops at remainder 0, and the last divisor, which is the last non-zero remainder, is the gcd. Indian texts set this out compactly, writing each new division just below and to the right of the one before. Fig. 11.9 follows the chain for $\gcd (1155,546)$.

The same pair takes 13 subtractions with EUCLID-SUB but only 4 divisions here.

Why is EUCLID-DIV so quick in general? A remainder is always smaller than its divisor. With a little more care one can show something stronger: after any two divisions, the larger number of the pair has dropped below half its old value. Each digit of a number can survive only about $3\frac{1}{3}$ halvings, so the count of divisions grows with the number of digits. A complete proof waits for a later class; for now, test the claim in the stepper.