Class 9 › Mathematics › Chapter

The World of Algorithms

What an algorithm is, the digit-by-digit addition algorithm, algorithms for the greatest common divisor (listing divisors, improvements, Euclid's subtraction method and Āryabhaṭa's division method), data structures, correctness and efficiency.

1. What is an Algorithm?
Algorithm: a step-by-step procedure to arrive at an answer; a systematic procedure to solve a problem. It is described by writing the steps as precisely as possible.
  • Precise steps: an algorithm must be followed exactly as written. You should not need to guess or perform any action that is not stated.
  • Basic steps: every algorithm is built from basic steps that we assume we can perform directly (for example, adding two single-digit numbers, or checking whether a smaller number divides a larger one).
  • Repetition: the same step may be executed many times, for example, "for each $j$ in $1, 2, \dots, n$".
  • Conditional steps: a step may happen only if a condition holds, for example, "add $j$ to the list only if $j$ divides $n$".
  • Names for values: we give names to the values the algorithm keeps track of (such as , or ). Without names, the steps would be clumsy to describe.
  • Executing: running through an algorithm step by step is called executing it.
  • A class of problems: an algorithm works for every input of its kind (any two numbers), not only for one instance.
  • Three jobs for every algorithm: describe it precisely, justify that it gives the correct answer, and analyse how many steps it takes compared with the size of the input.
2. Adding Numbers Digit by Digit
  • Addition by counting: draw dots for the first number, then for the second, and count all the dots. This is how addition is defined, but it is very slow for large numbers.
  • The faster way: write the numbers one below the other in the Indian place-value system, align the rightmost digits, and add column by column from right to left, passing a carry to the left.
  • Why align from the right: digits in the same column have the same place value (units with units, tens with tens). Only quantities of the same place value can be added directly.
  • Why the carry is never more than 1: the largest possible column total is $9 + 9 + 1 = 19$. Its units digit is written down and the carry is $1$.
  • Why Step 5 is needed: if the leftmost column produces a carry of $1$ and Step 5 is missing, the answer loses its leading digit and is wrong. When the last carry is $0$, the algorithm gives the correct result even without Step 5.
  • Carry condition: a column total of exactly $10$ also produces a carry. The rule is "$10$ or more", not only "more than $10$".
  • Numbers of different lengths: the steps assume both numbers have a digit in every column. When one number runs out of digits, treat its missing digits as $0$ so the carry can keep moving left.
  • Decimal fractions: align the decimal points (so equal place values line up), fill the shorter number with zeros on the right, add exactly as before, and place the decimal point in the answer directly below the other decimal points.
  • Assumption: we already know how to add single-digit numbers without counting.
3. Justifying and Comparing Algorithms
Why carrying is valid $$10 \text{ units} = 1 \text{ ten}, \qquad 10 \text{ tens} = 1 \text{ hundred}, \qquad 10 \text{ hundreds} = 1 \text{ thousand}, \dots$$
  • Justification (grouping): every number is grouped into units, tens, hundreds, and so on. Adding the two numbers is the same as adding each group separately. Whenever a group reaches ten, those ten make one of the next larger group, so we carry that one over. Carrying only changes how the total is written, not its value.
  • Counting is slow: if we can count one dot per second, then going from 3-digit to 4-digit numbers gives $10$ times as many dots, and going to 5-digit numbers gives $100$ times as many.
  • Digit-by-digit is fast: each extra digit adds only one more column. Going from 3 digits to 4 digits adds $1$ column, and to 5 digits adds $2$ columns.
In simple words: a good algorithm keeps its work in step with the length of the numbers (digits), not their size (value). This is the standard against which later algorithms in this chapter are judged.
4. Greatest Common Divisor: Breaking Down the Problem
Greatest common divisor (gcd) or highest common factor (hcf): the largest number that divides both of the given numbers.
Designing an algorithm from the definition
1. Understand what is required: the largest number that divides both numbers.
2. Break the problem into smaller pieces we already know how to solve:
  (a) compute the divisors of the first number and note them down;
  (b) compute the divisors of the second number and note them down;
  (c) compare the two collections and pick the largest number present in both.
  • Why start here: other methods exist (prime factorisation, for example), but an algorithm built straight from the definition is easy to justify as correct.
  • Strategy: splitting a big problem into smaller steps that are already solved is the key habit in designing algorithms.
5. Computing the Divisors of a Number
  • Divisors = factors: every divisor of $n$ lies between $1$ and $n$. The simplest method is to check each number from $1$ to $n$ and see whether it divides $n$.
  • List: to remember the divisors found so far, we keep them in a sequence called a list, written in square brackets. The empty list is $[\;]$.
  • Building the list: start with an empty list. Each time a new divisor is found, add it at the end.
  • Executing: at each $j$ either the list grows by one number (if $j$ divides $n$) or it stays unchanged (if it does not).
  • Output is in increasing order: $j$ is checked systematically from $1$ upward, so the list comes out sorted. It always starts with $1$ and ends with $n$, because both always divide $n$.
  • Basic step assumed: we know how to tell whether a smaller number divides a larger number.
  • Amount of work: $n$ checks are needed, so the work grows as the number grows.
6. First Algorithm for gcd
  • Reusing an algorithm: Steps 1 and 2 use the divisors algorithm as a building block. Larger algorithms are made from smaller ones.
  • Why the rightmost element: is in increasing order, so is also in increasing order. Its rightmost element is the largest common divisor, which is the gcd.
  • The list is never empty: $1$ divides every number, so $1$ is always a common divisor.
  • Why we need an algorithm: for large numbers the lists are very long, and it is no longer possible to find the largest common element by inspection. A systematic procedure is needed.
7. Data Structures
Data structure: a way of organising information so that an algorithm can use it efficiently. A list is an example of a data structure.
  • Intermediate quantities: while an algorithm runs, it computes values along the way, such as the lists of divisors. We name them (for example ) so that we can refer to them later.
  • More than simple numbers: these values are often more complicated than single numbers. Here they are lists, and in fact lists arranged in ascending order.
  • Why it matters: a well-chosen data structure makes an algorithm shorter to describe and faster to run. This idea is explored further in higher classes.
8. Improving the Algorithm
  • Why the last update is the gcd: $k$ increases from $2$ upward, so the last number that divided both is the largest common divisor.
  • Scanning backwards: if we scan from $\min(m, n)$ down to $1$, the first $j$ that divides both is already the gcd, so the scan can stop there. If the divisors of a number are listed from $n$ down to $1$, the list comes out in decreasing order, and the gcd becomes the leftmost common divisor instead of the rightmost.
  • Divisors occur in pairs: if $j$ divides $n$, then so does $\dfrac{n}{j}$. Checking only up to $\sqrt{n}$ finds every divisor, because each one comes with its partner (a repeated pair is counted once).
  • Caution with pairs: a list built in pairs is not in increasing order, so "take the rightmost element" no longer gives the largest. The list must be sorted, or the largest common divisor must be picked out explicitly.
  • Correctness is preserved: each refinement changes how the work is organised, not what is computed.
9. Analysing the Algorithms
  • Correctness: the first algorithm follows directly from the definition of gcd, so it is easy to justify. Every refinement keeps the same result, so all the versions give the correct gcd.
  • Efficiency: even the final version examines every number from $1$ to $\min(m, n)$. If the smaller number grows from 3 digits to 4 digits, the scan is $10$ times as long; for 5 digits, $100$ times as long.
  • Same problem as counting: the work is proportional to the value of the number, not to the number of digits used to write it.
  • The goal: find an algorithm for gcd whose effort is proportional to the number of digits, just as column addition is.
In simple words: to judge an algorithm, count how its number of steps grows when the input gets bigger. Steps growing with the value is slow; steps growing with the digits is fast.
10. Euclid's Subtraction Algorithm
Key observation (for $m \ge n$) $$\gcd(m, n) = \gcd(n,\, m - n)$$ Stopping case $$\gcd(m, 0) = m$$
Why $\gcd(m, n) = \gcd(n, m - n)$
1. Let $d$ be a common divisor of $m$ and $n$. Write $m = ad$ and $n = bd$ for natural numbers $a, b$. Then $m - n = ad - bd = (a - b)d$, so $d$ also divides $m - n$.
2. Conversely, let $d$ divide both $n$ and $m - n$: $n = xd$ and $m - n = yd$. Then $m = n + (m - n) = xd + yd = (x + y)d$, so $d$ also divides $m$.
3. Hence the pairs $(m, n)$ and $(n, m - n)$ have exactly the same set of common divisors, so their greatest common divisor is the same.
  • Reducing a problem to a simpler one: the new pair involves smaller numbers, so the problem becomes easier. The same step is applied again and again.
  • Purpose of Step 1: it ensures $m \ge n$, so that $m - n$ is never negative.
  • When to stop: the gcd of a number with itself is that number. Reducing $\gcd(m, m)$ gives $\gcd(m, 0)$, so once the second number becomes $0$ the answer is the first number.
  • Still slow: when one number is much smaller than the other, the same small number is subtracted many times. For example, $\gcd(2k + 1, 2)$ needs about $k$ reductions before the answer $1$ appears.
  • Conclusion: the number of steps is proportional to the value of the numbers, not to their number of digits. The original goal has not yet been reached.
  • History: Euclid wrote this method in his book Elements. Other Greek mathematicians probably knew it earlier, but he was the first to put it in writing.
11. Āryabhaṭa's Division Algorithm
Improved reduction step (for $m \ge n$) $$\gcd(m, n) = \gcd(n,\; m \bmod n)$$
$m \bmod n$: the remainder when $m$ is divided by $n$.
  • The idea: repeatedly subtracting $n$ from $m$ until you cannot subtract any more leaves exactly the remainder of $m \div n$. So all those subtractions can be replaced by a single division.
  • Why it is still correct: by the same argument as before, a divisor $d$ divides both $m$ and $n$ if and only if it divides both $n$ and $m \bmod n$. The pairs share the same common divisors, so the gcd is unchanged.
  • Only one change: in Euclid's algorithm, Step 3 changes from "$\gcd(n, m - n)$" to "$\gcd(n, m \bmod n)$". The stopping condition stays the same.
  • Long-division form: divide the larger number by the smaller one. Then divide the previous divisor by the remainder, and keep repeating. The divisor in the division whose remainder is $0$ is the gcd.
  • Speed: the number of reductions is now proportional to the number of digits of $m$ and $n$, which meets the goal of the chapter. The proof of this fact is left for later classes.
  • Large gap between numbers: a case such as $\gcd(2k + 1, 2)$ now needs only two reductions, however large $k$ is.
  • Source: this "long division" method appears in Indian treatises such as Āryabhaṭa's Āryabhaṭīya (499 CE), using Indian place-value numerals.
  • Common mix-up: $m \bmod n$ is a remainder, not the difference $m - n$.
12. A Pinch of History
Where the word "algorithm" comes from
Al-Khwārizmī (780–850 CE), a Persian mathematician at the "House of Wisdom" in Baghdad, admired Indian mathematics and learnt Sanskrit.
Around 820 CE he wrote a detailed treatise on the Indian place-value number system and the Indian procedures for the four operations: addition, subtraction, multiplication and division.
His original is lost, but its 12th-century Latin translation, Liber Algorismi de numero Indorum ("The Book of Al-Khwārizmī on Indian Numerals"), survives and helped spread Indian arithmetic through medieval Europe.
The Latin form of his name, Algoritmi, gave algorismus, meaning any Indian method of computing with numbers. It later became algorism and then algorithm.
  • Meaning today: the word first meant an Indian method of arithmetic. It later broadened to mean any well-defined, step-by-step, systematic procedure for solving a class of problems.
  • Euclid: first to write down the subtraction algorithm for gcd, in Elements.
  • Āryabhaṭa (499 CE): long-division method for gcd in the Āryabhaṭīya.
13. Summary and Quick Revision
Common mistakes:
• Not aligning the digits from the right while adding.
• Leaving out Step 5 (the final carry) in the addition algorithm.
• Forgetting that a column total of exactly $10$ also gives a carry.
• Assuming $1$ is not a common divisor, or forgetting that $1$ and $n$ are always divisors of $n$.
• Starting Euclid's algorithm with $m < n$ without reversing the numbers.
• Reporting $n$ instead of $m$ when $n = 0$; the answer at that point is $m$.
• Confusing $m \bmod n$ (the remainder) with $m - n$.
• Taking the "rightmost element" as the gcd when the list is not in increasing order.
• Thinking a faster-looking refinement changes the answer; it changes only the amount of work.
• Believing Euclid's subtraction algorithm takes steps in proportion to the number of digits; only the division version does.