Question

Foundations of algorithm chp 11 #15

15. write an iterative version of Algorithm 11.1. Your algorithm should only use a constant amount of memory li e., the space complexity function in 601)l. is

Answer 1

The iterative version for given algorithm goes like:

Code:

int gcd ( int n, int m) // assuming n > m else swap those

{

int rem;

while(m!=0)

{

rem = n%m;

n = m;

m = rem;

}

return n;

Explanation:

In this algorithm, the goal is to find the GCD but without using recursion. So, the technique that can be used is as below:

The method to understand it in both recursive and iterative I am considering same as working is same, just the code is different.

Say for instance one needs GCD of 300 and 21. So, the way to find it is, dividing greater number every time so that it shrinks and savingi the remainder. Say for instance, if 21 is not GCD, it will be obiously less than 21. So, to find it out, again division is done but with respect to the remainder. So, GCD(300,21) turns into GCD(21,6). Again, if 21 mod 6 is 0, 6 is GCD, but it is not. The remainder is 3. So, again, in the same way as previous, GCD of 6 and 21%6=3 is found which is 3. so, in turn the GCD is 3.

So, when remainder becomes 0, the other number is given as GCD.