The World of Algorithms Class 9: Notes, Euclid's and Āryabhaṭa's Methods

What The World of Algorithms is about

Key concepts

What an algorithm is

NCERT section 11.1 Adding Numbers

An algorithm is a systematic, step-by-step procedure that solves every problem of a certain kind. Its steps must be precise: someone (or a computer) following them exactly, doing nothing that is not written, must reach the right answer.

Algorithms are built from basic steps we can already do (such as adding two single digits). They often repeat a step (for each column…) and include conditions (if the sum is 10 or more, carry 1). For every algorithm we should also:
1. justify that it always gives the correct answer, and
2. analyse how much work it needs as the input grows.

Worked example

Write the column-addition algorithm as precise steps and follow it for $2486+3759$.

Try it first, then show the solutionSolution

1. Steps: (1) write the numbers with digits aligned from the right; (2) add the rightmost digits, write the units digit, set carry to 1 if the sum is 10 or more, else 0; (3) move left, add the two digits and the carry, and do the same; (4) repeat until no digits are left; (5) if carry is 1, write 1 at the left.
2. Units: $6+9=15$: write 5, carry 1.
3. Tens: $8+5+1=14$: write 4, carry 1.
4. Hundreds: $4+7+1=12$: write 2, carry 1.
5. Thousands: $2+3+1=6$: write 6, carry 0. Answer 6245.

Answer: 6245

Why column addition works, and why it is fast

NCERT section 11.1 Adding Numbers

Correctness: place value groups each number into units, tens, hundreds, … Adding column by column adds each group separately; when a group reaches ten, the ten is carried as one unit of the next group. The carry can never be more than 1, because the largest column sum is $9+9+1=19$.

Efficiency: counting dots for 4-digit numbers needs about 10 times the work of 3-digit numbers, but the column method needs just one more column. So the work grows with the number of digits, not with the value. NCERT's estimate: counting one dot a second, $3347+2729$ takes over 1 hour 40 minutes; adding columns at 15 seconds each takes about a minute.

Worked example

Why can the carry in column addition never be 2? What would go wrong if the last step ('if carry is 1, write 1 on the left') were left out?

Try it first, then show the solutionSolution

1. The biggest column total is two 9s plus a carry of 1: $9+9+1=19$, which is less than 20, so the carry is at most 1.
2. Without the last step, a final carry would be lost: $700+500$ would give 200 instead of 1200.
3. Additions with no final carry, like $123+456=579$, would still come out right.

Answer: The largest column sum is 19; without the last step, sums with a final carry lose their leading 1.

A first gcd algorithm, from the definition

NCERT section 11.2 Greatest Common Divisor

The gcd (greatest common divisor, also called HCF) of m and n is the largest number dividing both. Breaking the problem into smaller pieces gives an algorithm:
1. List the divisors of m (check each number from 1 to m).
2. List the divisors of n.
3. Keep the numbers that are in both lists (common divisors).
4. Report the largest (the rightmost in the ascending list).

It is clearly correct, because it follows the definition. Improvements: scan both numbers in one pass, then stop at $\min (m,n)$ and remember only the most recent common divisor, so no lists are needed. Even so, the work grows with the size of the numbers.

Worked example

Use the definition-based algorithm to find gcd(36, 84).

Try it first, then show the solutionSolution

1. Divisors of 36: 1, 2, 3, 4, 6, 9, 12, 18, 36.
2. Divisors of 84: 1, 2, 3, 4, 6, 7, 12, 14, 21, 28, 42, 84.
3. Common divisors: 1, 2, 3, 4, 6, 12.
4. Largest: 12.

Answer: gcd(36, 84) = 12

Data structures: lists

NCERT section 11.3 Data Structures

While an algorithm runs, it produces intermediate values, such as the list of divisors of m. Giving them names (divisors-of-m, common-divisors) lets later steps refer to them. Organising them in a sensible form, such as a list in increasing order, is called using a data structure.

A good data structure can make an algorithm simpler and faster: with two sorted lists you can find common elements by moving through both lists together once, instead of comparing every pair.

Worked example

List 1 = [2, 5, 8, 11, 14] and List 2 = [3, 5, 9, 11, 15], both in increasing order. Describe a one-pass method to find the elements of List 1 that are not in List 2, and give the answer.

Try it first, then show the solutionSolution

1. Point to the first element of each list.
2. If the List 1 element is smaller, it cannot appear later in List 2: record it and move along List 1.
3. If the elements are equal, it is common: skip it and move along both lists.
4. If the List 2 element is smaller, move along List 2.
5. Result: 2, 8, 14.

Answer: 2, 8 and 14

Euclid's subtraction algorithm

NCERT section 11.3 Data Structures

Key fact: if $m\ge n$, then $\gcd (m,n)=\gcd (n,m-n)$. Any d that divides m and n also divides $m-n$ (as $ad-bd=(a-b)d$), and any d that divides n and $m-n$ also divides their sum m. So the two pairs have exactly the same common divisors. In pictures: blocks of size d that tile m and n also tile $m-n$.

Algorithm (written down in Euclid's *Elements*):
1. If $m<n$, swap them.
2. If $n=0$, the answer is m.
3. Otherwise, replace the pair by $(n,m-n)$ and repeat.

It is correct, but can be slow: gcd(99, 2) needs about 49 subtractions.

Worked example

Use Euclid's subtraction algorithm to find gcd(84, 36). How many reductions are needed?

Try it first, then show the solutionSolution

1. (84, 36) → (36, 48); swap to (48, 36).
2. (48, 36) → (36, 12).
3. (36, 12) → (12, 24); swap to (24, 12).
4. (24, 12) → (12, 12) → (12, 0).
5. n = 0, so the answer is 12, after 5 reductions.

Answer: gcd = 12, after 5 reductions

Āryabhaṭa's division algorithm

NCERT section 11.3 Data Structures

Repeatedly subtracting n from m until you cannot any more leaves the remainder of m divided by n, written $m\mathrm{mod}n$ (for example, $17\mathrm{mod}5=2$). So one division does many subtractions at once:
$\gcd (m,n)=\gcd (n,m\mathrm{mod}n)$
The steps are the same as Euclid's, except step 3 uses the remainder. This is the long-division method for the gcd found in Āryabhaṭa's Āryabhaṭīya (499 CE). The number of steps grows only with the number of digits, like column addition.

The word algorithm comes from Al-Khwārizmī (c. 820 CE), who learnt Sanskrit and wrote about Indian arithmetic; the Latin form of his name came to mean an Indian method of calculation.

Worked example

Find gcd(252, 198) with Āryabhaṭa's division algorithm, and gcd(99, 2), counting the reductions in each.

Try it first, then show the solutionSolution

1. $252\mathrm{mod}198=54$: (198, 54).
2. $198\mathrm{mod}54=36$: (54, 36).
3. $54\mathrm{mod}36=18$: (36, 18).
4. $36\mathrm{mod}18=0$: (18, 0), so the gcd is 18 after 4 reductions.
5. gcd(99, 2): $99\mathrm{mod}2=1$ gives (2, 1), then (1, 0): gcd 1 in 2 reductions, instead of about 49 by subtraction.

Answer: gcd(252, 198) = 18 (4 reductions); gcd(99, 2) = 1 (2 reductions).

Maths in real life: The World of Algorithms

Each concept, met in an everyday situation. Read the situation, try the problem, then check the solution. The one-line hook is what to remember.

Topics in this chapter

• Column Addition, Lists and the Efficiency of Algorithms
• Computing the GCD: Definition, Euclid's Subtraction and Āryabhaṭa's Division

The World of Algorithms formula sheet

Definition

$\text{algorithm}=\text{precise, step-by-step procedure for a class of problems}$

Must be justified (correct) and can be analysed (efficient).

Carry in addition

$9+9+1=19<20\Rightarrow \text{carry}\le 1$

Euclid's reduction

$\gcd (m,n)=\gcd (n,m-n)(m\ge n)$

Āryabhaṭa's reduction

$\gcd (m,n)=\gcd (n,m\mathrm{mod}n)$

Stopping rule

$\gcd (m,0)=m$

Remainder notation

$m\mathrm{mod}n=\text{remainder when }m\text{ is divided by }n$

e.g. $33\mathrm{mod}7=5$.

Work needed

$\text{counting or listing: grows with the value};\text{column addition, division gcd: grows with the number of digits}$

Tricks to remember The World of Algorithms

Short memory aids. Say each one aloud once, then use it on a question the same day.

• Precise, Correct, Quick

  A good algorithm is Precise (no guessing), Correct (justified) and Quick (efficient).

  Use it when: Judging or describing any algorithm.

• Subtract many times = divide once

  What is left after subtracting n again and again is just the remainder.

  Use it when: Seeing why Āryabhaṭa's method is a fast version of Euclid's.

• Zero means done

  When the second number becomes 0, the first number is the gcd.

  Use it when: The stopping rule of both gcd algorithms.

• Al-Khwārizmī gave us the word

  Algoritmi (Latin for Al-Khwārizmī) became 'algorithm'.

  Use it when: Remembering the history of the word.

NCERT exercise guide: The World of Algorithms

What each exercise in the NCERT chapter tests, how to approach it, and a question of the same kind solved step by step. Questions here are written in our own words.

Test your recall

Answer in your head or on paper first, then open the card. Pulling an answer out of memory makes it stick far better than re-reading.

1. 1.What is an algorithm?Show answer

   A precise, step-by-step procedure that solves every problem of a given type.

2. 2.Name two things we should do for every algorithm, besides writing its steps.Show answer

   Justify that it is correct, and analyse how efficient it is.

3. 3.Why is the carry in column addition at most 1?Show answer

   The largest column sum is 9 + 9 + 1 = 19.

4. 4.State Euclid's key fact for the gcd.Show answer

   For $m\ge n$, $\gcd (m,n)=\gcd (n,m-n)$.

5. 5.How does Āryabhaṭa's method improve on Euclid's subtraction?Show answer

   It uses the remainder, $\gcd (n,m\mathrm{mod}n)$, doing many subtractions in one division.

6. 6.What is gcd(m, 0)?Show answer

   m

7. 7.What is a data structure?Show answer

   A way of organising intermediate values (such as a sorted list) so an algorithm can use them easily.

8. 8.Where does the word 'algorithm' come from?Show answer

   From the Latin form of the name of Al-Khwārizmī, who wrote about Indian arithmetic.

Quick revision checklist

The night before the exam: can you do each of these without looking?

• ☐Can you define an algorithm in one sentence?
• ☐Can you follow the addition algorithm on a 5-digit plus 3-digit sum?
• ☐Can you explain why the carry is never 2?
• ☐Can you find gcd(48, 180) by listing divisors?
• ☐Can you prove that a common divisor of m and n also divides m − n?
• ☐Can you find gcd(210, 98) with Āryabhaṭa's division algorithm?
• ☐Can you explain why the division method needs fewer steps?

The World of Algorithms: frequently asked questions