Class 9 Mathematics Chapter 11: The World of Algorithms

An algorithm is a precise step-by-step procedure that arrives at an answer, described so that each step can be followed without judgement. The column method for adding two numbers is an example.

So that digits of the same place value fall in the same column. The method adds units to units and tens to tens, so a right alignment is what makes each column one place-value group.

The largest total a column can reach is $9+9+1=19$. That forms exactly one new group of ten, so only 1 is ever carried.

Without Step 5 the final carry is never written, so the answer loses its leading digit whenever the leftmost column overflows. $473+695$ would read 168 instead of 1168. If the leftmost column totals less than ten, as in $123+45$, there is no final carry and the answer is unaffected.

Counting grows with the size of the number: one more digit means ten times as many dots. The column method grows with the number of digits: one more digit means one more column. Going from 3-digit to 5-digit numbers is a hundred times the dots but only two extra columns.

It assumes we can add two single digits without counting them out. That is acceptable because every algorithm is built from basic steps taken as given; without some such step the description would never end.

Yes. Aligned on the right, the two highest columns contain a digit from the longer number only. Step 3 adds that digit to the incoming carry, which the steps already allow, so nothing has to change.

Each number is a sum of place-value groups: units, tens, hundreds and so on. Addition can be regrouped, so the totals of corresponding groups can be added separately. Whenever a group of units reaches ten it forms one new ten, which is carried into the tens group. Doing this column by column therefore produces the same total as combining and counting everything at once.

Write the numbers with their decimal points aligned rather than their right-hand edges, padding with zeros so both have the same number of decimal places. This is the same rule, because aligning on the right was only ever a way of making place values meet, and the decimal point is where the place values turn from units to tenths.

Addition is defined by combining and counting. The algorithm is a faster procedure that is claimed to give the same answer, so it is the algorithm that needs justifying against the definition, not the other way round. That justification is the grouping argument.

Steps. 1 Write the numbers one below the other with digits aligned from the right. 2 Add the units, writing the total if it is under ten and setting the carry to 0, or writing the units digit and setting the carry to 1 if it is ten or more. 3 Move one column left and add the two digits and the carry, applying the same rule. 4 Repeat until no digits remain. 5 If the carry is 1 at the end, write it to the left.

Working: units $9+9=18$, write 8 carry 1; tens $8+3+1=12$, write 2 carry 1; hundreds $5+4+1=10$, write 0 carry 1; thousands $4+3+1=8$, write 8 carry 0. No final carry, so the answer is 8028.

Counting is driven by the size of the number. Each extra digit multiplies the quantity of dots by ten, so 3-digit numbers give ten times the dots of 2-digit ones and 5-digit numbers a hundred times the dots of 3-digit ones. The column method is driven by the number of digits: each extra digit adds exactly one column. Concretely, one dot a second makes $33+27$ a minute's work, $334+272$ ten times that, and $3347+2729$ a little over a hundred minutes. At fifteen seconds a column the same three sums take about half a minute, about forty-five seconds and about one minute.

They will be right whenever the leftmost column totals less than ten, because then the carry is 0 at the end and there is nothing for Step 5 to write. $123+45$ or $412+376$ are unaffected. They will be wrong whenever the leftmost column reaches ten or more, losing the leading digit: $473+695$ gives 168 rather than 1168, and $56+55$ gives 11 rather than 111. The mistake is hard to notice because the procedure still terminates normally and produces a plausible-looking number; nothing about the steps signals that anything was dropped.

Addition is defined by combining two collections and counting the result. Any whole number can be written as a sum of place-value groups, so $473$ is four hundreds, seven tens and three units. Combining two numbers therefore combines their groups, and since the order of addition does not matter, corresponding groups can be totalled separately. When a group reaches ten it is exactly one group of the next size, which is why it can be carried one place left rather than counted again. Working column by column from the right performs precisely this grouping, so it yields the same total as counting everything. The algorithm assumes two basic steps: that single digits can be added without counting, and that numbers are written in the base-ten place-value system.

$[1, 2, 3, 6, 9, 18]$. The algorithm tests $j$ from 1 upwards and appends each divisor as it is found, so the list is increasing without any sorting step.

Because 1 divides every number, so 1 is a common divisor of any pair. The gcd is therefore at least 1.

It reports the rightmost entry of the common-divisor list. That is enough because both divisor lists were built in increasing order, so the common list increases too and its last entry is the greatest.

divisors(375) is $[1, 3, 5, 15, 25, 75, 125, 375]$ and divisors(825) is $[1, 3, 5, 11, 15, 25, 33, 55, 75, 165, 275, 825]$. Checking each entry of the first against the second keeps $[1, 3, 5, 15, 25, 75]$, since 125 and 375 are missing from the second list. The rightmost entry is 75, so $\gcd(375, 825) = 75$.

It makes 775 tests, one for each $j$ from 1 to 775, and finds $[1, 5, 25, 31, 155, 775]$. The cost therefore depends on the size of the number rather than on how many divisors it turns out to have.

Because $n$ divides itself and belongs in its own divisor list. Stopping early would leave it out, and it is needed for cases such as $\gcd(375, 375)$, whose answer is 375.

Every entry of the common-divisor list divides both numbers, and a divisor of a number cannot be larger than that number. So every common divisor is at most the smaller number, and the greatest of them is too.

Steps 1 and 2 are each a call to the divisors algorithm, once on $m$ and once on $n$. Because that algorithm was written out precisely -- start with an empty list, test every $j$ from 1 to $n$, append on discovery -- it can be invoked as a single step here without restating it. Its guarantee that the list comes out in increasing order is what lets step 5 simply read off the last entry.

Each number has 80 divisors, so the two lists are far too long to scan reliably for the largest shared value. What replaces it is an explicit step: start an empty common list, and for each entry of the first list check whether it appears in the second, appending it if so. The 64 shared entries then end at 27000, which is the gcd.

It is correct because it works directly from the definition: it finds every divisor of each number, keeps exactly those that are common, and reports the greatest. Nothing is assumed beyond being able to test divisibility. It is slow because the work grows with the numbers themselves: $\gcd(54000, 81000)$ needs 81000 divisibility tests to produce an answer of 27000, and almost all of those tests fail.

Algorithm: 1 start with an empty list-of-divisors; 2 for each $j$ in $1, 2, \ldots, n$, if $j$ divides $n$ then append $j$ to list-of-divisors.

Executing for 15: the list begins empty. 1 divides 15, giving $[1]$. 2 does not. 3 divides 15, giving $[1, 3]$. 4 does not. 5 divides 15, giving $[1, 3, 5]$. 6 to 14 do not divide 15. 15 divides itself, giving $[1, 3, 5, 15]$.

The basic step assumed is that we can tell whether a smaller number divides a larger one.

Algorithm: 1 let divisors-of-m be divisors($m$); 2 let divisors-of-n be divisors($n$); 3 start with an empty list common-divisors; 4 for each $x$ in divisors-of-m, if $x$ also appears in divisors-of-n then append $x$ to common-divisors; 5 report the rightmost entry of common-divisors as $\gcd(m, n)$.

On 375 and 825: divisors(375) is $[1, 3, 5, 15, 25, 75, 125, 375]$ and divisors(825) is $[1, 3, 5, 11, 15, 25, 33, 55, 75, 165, 275, 825]$. Of the eight entries in the first list, 125 and 375 are absent from the second, so common-divisors is $[1, 3, 5, 15, 25, 75]$. Its rightmost entry is 75, so $\gcd(375, 825) = 75$.

Each divisor list is built by testing $j$ from 1 upwards and appending every divisor as it is found, so each list is in increasing order by construction, with no sorting step. Step 4 walks the first list from left to right and appends the entries that also appear in the second, so it preserves that order and the common list increases too.

It matters because step 5 can then simply read the rightmost entry. Without the ordering guarantee the algorithm would need an extra step to search the common list for its largest member, and the justification for the answer being the greatest common divisor would have to be made separately.

The observation is true: apart from $n$, every divisor of $n$ is at most $n/2$. So testing $j$ beyond $n/2$ finds nothing new except $n$ itself. The proposal as stated is nonetheless wrong, because it would leave $n$ out of its own divisor list, and $n$ is needed: $\gcd(375, 375)$ must come out as 375, and divisors(18) must end at 18.

The repair is to test $j$ up to $n/2$ and then append $n$ directly, which keeps every list correct and roughly halves the testing. It is still slow, because the work remains proportional to $n$.

For $m \geq n$, $\gcd(m, n) = \gcd(n, m - n)$. The process stops when the second number reaches 0, and then the answer is the first number.

A data structure is a way of organising information so that an algorithm can work more efficiently. The chapter uses lists, kept in ascending order.

Step 3. Euclid reduces $\gcd(m, n)$ to $\gcd(n, m - n)$; Aryabhata reduces it to $\gcd(n, m \bmod n)$. Steps 1 and 2 are identical.

Let $d$ be a common divisor, so $m = ad$ and $n = bd$ for natural numbers $a$ and $b$. Then $m - n = ad - bd = (a - b)d$, which is a multiple of $d$, so $d$ divides $m - n$.

$\min(6, 12) = 6$, and most-recent-common-divisor starts at 1. $k = 2$ divides both, so it updates to 2. $k = 3$ divides both, so it updates to 3. $k = 4$ and $k = 5$ do not divide 6, so it stays at 3. $k = 6$ divides both, so it updates to 6. The scan ends and the gcd is 6.

First, the two separate scans of $m$ and of $n$ are combined into one pass, cutting $m + n$ candidates to $\max(m, n)$. Second, the common divisors are computed directly rather than building two lists and comparing them. Third, since no common divisor can exceed the smaller number, the scan need only run to $\min(m, n)$.

Subtracting 2 repeatedly from 99 takes about 51 reductions, because each step removes only 2. The division step goes straight to the remainder: $99 \bmod 2 = 1$ and then $2 \bmod 1 = 0$, so it finishes in two.

The first algorithm was derived straight from the definition of the gcd: it finds every divisor of each number, keeps the common ones and reports the greatest, so its correctness is immediate. Each refinement then changes only how much work is done -- combining scans, computing the common list directly, keeping one running value instead of a list, or reducing by difference or remainder -- while computing the same quantity. Since what is computed is unchanged, the original justification carries over to each of them.

The scanning versions are proportional to the VALUE of the smaller number: going from a 3-digit to a 5-digit number multiplies the work by a hundred. Euclid's subtraction version is no better in the worst case, since $\gcd(2k+1, 2)$ takes about $k$ reductions. Aryabhata's division version is the one that improves matters, because each remainder step can shrink the numbers enormously: $\gcd(99, 2)$ falls from 51 steps to 2.

The divisors of 18 pair up as $(1, 18)$, $(2, 9)$ and $(3, 6)$, so every divisor below the square root has a partner above it. Examining only the numbers up to about $\sqrt{n}$ therefore finds all of them, which is a large saving on scanning to $n$. The cost is that the divisors no longer arrive in ascending order, so the gcd algorithm can no longer simply report the rightmost entry of the common list; it would need a separate step to find the largest.

Algorithm: Step 1, when the first number is the smaller, swap the pair over. Step 2, once the second number has fallen to zero, the first number is the answer. Step 3, in every other case replace the pair by $(n, m - n)$ and begin again.

Applying it: $\gcd(375, 825)$ reverses to $\gcd(825, 375)$, then reduces through $\gcd(375, 450)$, $\gcd(450, 375)$, $\gcd(375, 75)$, $\gcd(75, 300)$, $\gcd(300, 75)$, $\gcd(75, 225)$, $\gcd(225, 75)$, $\gcd(75, 150)$, $\gcd(150, 75)$, $\gcd(75, 75)$ and finally $\gcd(75, 0)$. Step 2 then reports 75. There are seven Step-3 reductions in all.

Suppose $d$ is a common divisor of $m$ and $n$. Write $m = ad$ and $n = bd$. Then $m - n = (a - b)d$, so $d$ divides $m - n$ as well, and $d$ is therefore a common divisor of $n$ and $m - n$.

Now suppose instead that $d$ divides both $n$ and $m - n$. Write $n = xd$ and $m - n = yd$. Then $m = n + (m - n) = xd + yd = (x + y)d$, so $d$ divides $m$ and is a common divisor of $m$ and $n$.

The two pairs therefore have exactly the same set of common divisors, so they have the same greatest one. The chapter shows this as a tiling: blocks of size $d$ that fill $m$ and $n$ also fill the leftover $m - n$.

First, the two scans are merged: instead of running 1 to $m$ and then 1 to $n$, a single pass of $j$ from 1 to $\max(m, n)$ adds $j$ to whichever lists it divides. The candidates checked fall from $m + n$ to $\max(m, n)$.

Second, the common divisors are computed directly: for each $j$, if $j$ divides both numbers it goes into one common list. The two separate lists and the comparison step disappear. Since a common divisor cannot exceed the smaller number, the scan can stop at $\min(m, n)$.

Third, the list itself goes. Each larger common divisor makes the earlier ones useless, so a single value most-recent-common-divisor is kept, started at 1 and updated whenever a larger common divisor appears. At the end it holds the gcd.

Euclid reduces $\gcd(m, n)$ to $\gcd(n, m - n)$; Aryabhata reduces it to $\gcd(n, m \bmod n)$. The justification is the same in form: a divisor tiles $m$ and $n$ exactly when it tiles $n$ and the remainder.

The difference is speed. Subtracting is the slow way of finding a remainder: what is left when $n$ can no longer be taken from $m$ IS $m \bmod n$. So one division replaces a whole run of subtractions. On $\gcd(375, 825)$ subtraction needs seven reductions and division needs two. On $\gcd(99, 2)$ the gap is extreme: subtraction grinds down 97, 95, 93 and so on for about 51 steps, while division gives $99 \bmod 2 = 1$ and then $2 \bmod 1 = 0$ in two.

Only the division version approaches the chapter's goal of effort proportional to the number of digits rather than to the value.

An algorithm is a precise step-by-step procedure that arrives at an answer, described so that each step can be followed without judgement. The column method for adding two numbers is an example.

So that digits of the same place value fall in the same column. The method adds units to units and tens to tens, so a right alignment is what makes each column one place-value group.

The largest total a column can reach is $9+9+1=19$. That forms exactly one new group of ten, so only 1 is ever carried.

$[1, 2, 3, 6, 9, 18]$. The algorithm tests $j$ from 1 upwards and appends each divisor as it is found, so the list is increasing without any sorting step.

Because 1 divides every number, so 1 is a common divisor of any pair. The gcd is therefore at least 1.

It reports the rightmost entry of the common-divisor list. That is enough because both divisor lists were built in increasing order, so the common list increases too and its last entry is the greatest.

For $m \geq n$, $\gcd(m, n) = \gcd(n, m - n)$. The process stops when the second number reaches 0, and then the answer is the first number.

A data structure is a way of organising information so that an algorithm can work more efficiently. The chapter uses lists, kept in ascending order.

Step 3. Euclid reduces $\gcd(m, n)$ to $\gcd(n, m - n)$; Aryabhata reduces it to $\gcd(n, m \bmod n)$. Steps 1 and 2 are identical.