The World Of Algorithms
Suppose and are two lists of numbers in increasing order.
(i) Write an algorithm to find elements in that are not present in .
(ii) Write an algorithm to find elements in that are not present in .
Describe an algorithm to compute the least common multiple () of two numbers.
Divisors occur in pairs. For instance, the divisors of are , and .
(i) If we write out divisors in pairs, how many numbers do we have to examine between and to find all the divisors of ?
(ii) If we list out the divisors in pairs, will our gcd algorithm still work in the manner we have described?
11.3.1 Improving the Algorithm
Compute both lists of divisors together
In the algorithm above, we first check all numbers between and to find the divisors of . Then we start again with and check all numbers between and to find the divisors of . This means we have to scan possible divisors. We can combine these two scans into one. Let be the maximum of and . We run through each from to .
This reduces the number of possible divisors to be checked from to .
Directly compute the list of common divisors
If we combine the scans, we can directly compute the list of common divisors, instead of first computing the divisors of each number and then combining the lists.
In fact, a common divisor cannot be larger than the smaller of the two numbers, so we can check for common divisors up to the minimum of and rather than the maximum.
Do away with lists
Do we need to maintain the list of all common divisors? Each time we find a larger common divisor, the ones that we have found earlier are useless! Let us keep track of a quantity called most-recent-common-divisor. We know that is always a common divisor, so we can start with most-recent-common-divisor set to . We then scan all numbers from to .
At the end of this scan, most-recent-common-divisor directly gives us the gcd.