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?

Step-by-step solution

Idea: The original gcd algorithm reports the rightmost common divisor because the lists were in increasing order. Reversing the scan reverses the order of the lists, so the greatest common divisor moves to the other end.

1. Scanning j = n, n − 1, …, 1 finds the divisors from largest to smallest. For example divisors(18) becomes [18, 9, 6, 3, 2, 1], a decreasing list.½ mark
2. The gcd algorithm uses this same divisors procedure for both numbers, so divisors-of-m and divisors-of-n are both decreasing. Step 4 goes through divisors-of-m in order, so common-divisors is also built in decreasing order.½ mark
3. Now the greatest common divisor is the leftmost (first) element. Step 5 must change to: “Report the leftmost element of common-divisors as gcd(m, n)”. If Step 5 is left unchanged, it reports the rightmost element, which is always 1: wrong unless the gcd really is 1.1 mark
4. Example gcd(375, 825): divisors-of-m = [375, 125, 75, 25, 15, 5, 3, 1]; checking each in divisors(825) gives common-divisors = [75, 25, 15, 5, 3, 1]. Leftmost = 75 ✓.½ mark
5. Bonus: the first common divisor found is already the gcd, so we may stop there and skip the rest of the list.½ mark
6. Note: if only the list for the second number were reversed, nothing would change, because common-divisors follows the order of divisors-of-m and the membership check does not depend on order.

Answer to write in the exam

Common mistakes that cost marks

• Saying “nothing changes” while still reporting the rightmost element, which would now always be 1.
• Thinking the set of divisors changes. Only their order changes; the same divisors are found.
• Forgetting that the algorithm can now stop early, which is the real gain from scanning in reverse.

How this can come in the exam

Try one yourself

With divisors listed in decreasing order, find gcd(20, 30) by the original algorithm.

More questions like this

• 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?
• Let us assume that m ≥ n. Then, gcd(m, n) is the same as gcd(n, m − n). Why is this the case?
• Euclid’s algorithm for gcd(m, n): 1. If m < n, reverse the numbers and compute gcd(n, m) 2. If n = 0, report the answer as m 3. Otherwise, reduce the problem to compute gcd(n, m − n). Let us apply this algorithm to gcd(375, 825), the problem that we saw before.
• Are we close to our original goal of finding an algorithm where the effort is proportional to the number of digits?
• Consider the earlier example gcd(99, 2) that took a long time to converge. Here is what happens when we execute the improved algorithm.

All Algorithms questions · All maths questions