NCERT Solutions Class 9 Mathematics Ganita Manjari 2 Chapter 11 The World of Algorithms Exercise 11.3

Exercise Set 11.3

Question 1. How would our original algorithm change if we computed the divisors of n by examining the numbers from 1 to n in reverse order, from n down to 1?
Answer:
Testing j = n, n − 1, …, 2, 1 finds the divisors from largest to smallest, so every list of divisors comes out in decreasing order. For example, divisors(18) = [18, 9, 6, 3, 2, 1].
In the gcd algorithm, common-divisors is built by going through divisors-of-m in order, so it is also decreasing. The greatest common divisor is now the leftmost (first) element.
So the last step changes to:
5. Report the leftmost element of the list common-divisors as gcd(m, n).
Example: gcd(375, 825).
divisors-of-m = [375, 125, 75, 25, 15, 5, 3, 1]
divisors-of-n = [825, 275, 165, 75, 55, 33, 25, 15, 11, 5, 3, 1]
common-divisors = [75, 25, 15, 5, 3, 1]; the leftmost element is 75, so gcd(375, 825) = 75.
An extra saving: the first common divisor met is the largest, so Step 4 can stop as soon as it finds an x in divisors-of-m that is also in divisors-of-n. Here 375 (not in list), 125 (not in list), 75 (in list) → stop, gcd = 75. There is no need to build the whole list.
(Finding each list of divisors still needs n tests, so that part of the work is unchanged; only the order of the lists and the final step change.)

Question 2. What about the last algorithm described above? What happens when we look at common divisors starting from min(m, n) and work backwards to 1?
Answer:
Scanning k = min(m, n), min(m, n) − 1, …, 2, 1, the first k that divides both m and n is the largest common divisor, i.e. the gcd. So we need not keep updating most-recent-common-divisor; we report the first common divisor found and stop.
Algorithm gcd(m, n) scanning backwards
1. For each k from min(m, n) down to 1:
    — if k divides both m and n, report k as gcd(m, n) and stop.
It always stops, because k = 1 divides every number.
Example 1: m = 6, n = 12. min = 6, and k = 6 divides both, so gcd(6, 12) = 6 after only 1 test (the forward scan needed 5 tests, k = 2 to 6).
Example 2: m = 8, n = 12. k = 8: divides 8, not 12 → continue; k = 7: neither → continue; k = 6: divides 12, not 8 → continue; k = 5: neither → continue; k = 4: divides both → stop, gcd = 4.
Work needed: the number of tests is min(m, n) − gcd(m, n) + 1.
gcd(375, 825): 375 − 75 + 1 = 301 tests, instead of 374 going forwards (k = 2 to 375).
gcd(54000, 81000): 54000 − 27000 + 1 = 27001 tests, instead of 53999.
But when the gcd is small there is almost no saving: for gcd(99, 98) = 1 the backward scan tests k = 98, 97, …, 1, i.e. 98 numbers, about the same as the 97 tests (k = 2 to 98) of the forward scan.
Working backwards, the first common divisor found is the gcd, so we can stop at once and no list or updating is needed. This often saves work, but in the worst case (gcd = 1) we still test about min(m, n) numbers, so the work still grows with the value of the smaller number, not with its number of digits.

Teacher's Note:
1. Encourage students to count tests, not just find answers: the count is what measures how good an algorithm is.
2. The worst case (gcd = 1) is what matters when comparing algorithms, which motivates Euclid's method.