What about the last algorithm described above? What happens when we look at common divisors starting from and work backwards to 1?
The World of Algorithms · Question 10 of 15
What about the last algorithm described above?
In the last algorithm, most-recent-common-divisor is updated every time we find a common divisor. Scanning upwards, each new common divisor is larger, so the last one found is the gcd.
If we scan backwards, from down to 1, the common divisors appear in decreasing order. The first common divisor we meet is the greatest one, so it is the gcd. If we kept updating most-recent-common-divisor, it would be overwritten by smaller and smaller common divisors and end up as 1, which is wrong. So the algorithm changes to:
- For each from down to 1: if divides both and , report as gcd(m, n) and stop.
The scan always stops, at the latest when , because 1 divides every number. We do not even need the starting value 1 for most-recent-common-divisor.
Example 1: , . , and divides both 6 and 12, so after just 1 check (the upward scan needed 5 checks, to 6).
Example 2: gcd(375, 825). We check and the first dividing both is 75. That is checks, against checks for the upward scan from 2 to 375.
So working backwards gives the same answer and usually saves work, because we stop early. But in the worst case, when the gcd is 1, we still examine every number from down to 1; for example gcd(100, 99) takes 99 checks. The work still grows with the value of the numbers, not with the number of digits.
