0 solutions available
(i) Add 2356 and 4879 using the steps we have written down. Make sure you follow the steps precisely; do not perform any action that is not explicitly mentioned. Are you able to obtain the correct result?
What happens if you add a 5‑digit number to a 3‑digit number? Do our steps handle this situation correctly?
Why is it important to align the columns from right to left?
In Step 3, why cannot the value of carry be more than 1?
What happens if we do not include the fifth step in the algorithm above? Give examples where the algorithm will work correctly and where it will fail to work. There is also an important assumption in this algorithm, namely, that we know how to add single digit numbers without counting them out. Typically, any algorithm is built using such basic steps that we assume we can perform directly. The main advantage of this algorithm is that it is much faster than counting explicitly. For instance, if we move from adding 3-digit numbers to adding 4-digit numbers, we have 10 times as many dots to draw and count. On the other hand, if we add the digits right to left, as in the algorithm above, we only have to add 1 more column. Likewise, 5-digit numbers would generate 100 times as many dots as 3-digit numbers, but only 2 more columns to be added. In concrete terms, suppose we can count one dot per second. To count the dots in 33+27 would take a minute, to count 334+272 would take about ten minutes, while 3347+2729 would take over one hour and forty minutes. On the other hand, suppose we work slowly and carefully and take 15 seconds to add two single digit numbers with a carry. Adding 33+27 would take about half a minute, while 334+272 would take about 45 seconds, while 3347+2729 would take about one minute. Whenever we provide an algorithm, we also have to justify why it works. Combining the dots and counting the sum is how addition is defined. Why does adding individual digits from right to left result in the sum of the two numbers? The key idea is that we are grouping each number into units, tens, hundreds, … and adding each group separately. Whenever a smaller group, say units, generates a large group of ten, we carry over the newly formed ten to the tens group.
Suppose L1 and L2 are two lists of numbers in increasing order.
(i) Write an algorithm to find elements in L1 that are not present in L2.
(ii) Write an algorithm to find elements in L2 that are not present in L1.
Describe an algorithm to compute the least common multiple (lcm) of two numbers.
Divisors occur in pairs. For instance, the divisors of 18 are (1,18), (2,9) and (3,6).
(i) If we write out divisors in pairs, how many numbers do we have to examine between 1 and n to find all the divisors of n?
(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 1 and m to find the divisors of m. Then we start again with 1 and check all numbers between 1 and n to find the divisors of n. This means we have to scan m+n possible divisors. We can combine these two scans into one. Let max(m,n) be the maximum of m and n. We run through each j from 1 to max(m,n).
This reduces the number of possible divisors to be checked from m+n to max(m,n).
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 m and n 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 1 is always a common divisor, so we can start with most-recent-common-divisor set to 1. We then scan all numbers from 2 to min(m,n).
At the end of this scan, most-recent-common-divisor directly gives us the gcd.
Find gcd(99,75) using the Euclidean algorithm.
(i) gcd(825,375) (ii) gcd(375,75) (iii) gcd(16,60) (iv) gcd(12,16) (v) gcd(1,4) (vi) gcd(12,3)
(i) Find gcd(60,16).
(ii) Find gcd(16,12).
(iii) Find gcd(12,4).
Compute the following using the improved version of Euclid’s algorithm.
(i) gcd(375,825)
(ii) gcd(51000,81000)
(iii) gcd(1789287,237656)
(iv) gcd(2587392,157656)
Assume that m≥n. Verify that d divides m and n if and only if d divides both n and $m \bmod n,. $
Write an algorithm prime(n) to check if n is prime.
Hint: A prime number p has exactly two distinct factors, 1 and p. Can you make use of divisors(n) to write out prime(n)?
Write an algorithm primedivisors(n) to compute the list of divisors of n that are prime numbers.
(Hint: Compute divisors(n) and then filter out the primes in this list.)
We can also find the gcd of two numbers by computing the prime factorisation of both numbers. Try to write an algorithm to compute the prime factorisation of a number.
(i) The prime factorisation of 180 is 22×32×5. How would you represent this?
(ii) How would you compare the prime factorisations of two numbers?