Are we close to our original goal of finding an algorithm where the effort is proportional to the number of digits?

Step-by-step solution

Idea: Find a case where subtraction is slow: subtracting a small number from a big one again and again. Count the steps and compare with the number of digits.

1. Take gcd(99, 2). Each reduction subtracts 2: gcd(99, 2) → gcd(97, 2) → gcd(95, 2) → … → gcd(5, 2) → gcd(3, 2) → gcd(2, 1) → gcd(1, 1) → gcd(1, 0), giving the answer 1. Going from 99 down to 1 in steps of 2 takes 49 subtractions, and then 2 more: about 50 reductions for a 2-digit number.1 mark
2. In general gcd(2k + 1, 2) needs about k reductions. So gcd(999, 2) would need about 500, and gcd(9999, 2) about 5000: one more digit makes the work about 10 times larger. The number of steps is proportional to the value of the number, not to the number of digits.½ mark
3. So no, we are not close to the goal yet. (Replacing repeated subtraction by division, using the remainder, fixes this.)½ mark

Answer to write in the exam

Common mistakes that cost marks

• Judging from the gcd(375, 825) case alone (only 7 reductions). One fast case does not show the algorithm is always fast.
• Saying the number of steps grows by 1 for each extra digit. For gcd(2k + 1, 2) it grows about 10 times for each extra digit.
• Forgetting the last reductions gcd(2, 1) → gcd(1, 1) → gcd(1, 0) when counting.

How this can come in the exam

Try one yourself

How many times is 2 subtracted from 51 before the subtraction algorithm reaches gcd(2, 1)?

More questions like this

• Consider the earlier example gcd(99, 2) that took a long time to converge. Here is what happens when we execute the improved algorithm.
• In other words, we needed only two reduction steps to get to the final answer. Check that this would happen for any similar problem of the form gcd(2k + 1, 2).
• The above modified algorithm can be carried out concisely using the “long division” method given by Indians at least from the time of Āryabhaṭa. We illustrate the method through the following examples—
• Compute the following using the improved version of Euclid’s algorithm.
• Assume that m ≥ n. Verify that d divides m and n if and only if d divides both n and m mod n.

All Algorithms questions · All maths questions