GCD Algorithm is Euclid’s (Euclidean). Lab test Computer Programming I (TCP 1231)

GCD Flowchart

Today, when i was half sleeping, my junior buzzed me thru YM asking one of the question in his lab test. I dont know why and how he managed to get himself online so he can ask me this question. Well, since i was asked i just simply answer then. The question is about How to get GCD (Greatest Common Divisor) between 2 integers.  The answer is : apply Euclidean Algorithm.

GCD is something like this : When you have 33 and 21 in your hands, what is the greatest common integer which can divide both of those two integer? The answer is 3. We can get it thru using Euclid’s (Euclidean) Algorithm. In Programming not only the result is important, but also the algorithm itself. Algorithm is like a step-by-step procedure to achieve some goals. Simple saying, a recipe of a cooking/dish is also “an algorithm” for culinary word. So, to get GCD  we must formulate these steps in the previously said algorithm :

1) We assume they are positive nonzer0. Then, Here we can say 1st integer is m and 2nd one is n

if one of them is zero, then the gcd will be the nonzero number between those two.

2) set the greater and smaller integer between those two positive nonzero.

3)reduce the greater with the smaller until the greater now equals or less than the smaller. if so, swap the greater to become the smaller, and the smaller vice versa.

4) iterate the step above until one of them is equal with zero or less.

hence, the other number will be the GCD.

illustration:

100 and 36. What is the GCD?

greater = 100, smaller = 36. so, 100-36-36 = 28. now the greater (28) is lesser than smaller (36). swap them. now the greater is 36 and smaller is 28. do the same as before ( 36 – 28). it yields the greater now is 8 and the smaller is 28. swap again. now greater is 28, smaller = 8. do the same operation as before ( 28-8-8-8). The remainder is 4 before it subtracts 28 eventually become -4 ( As the remainder is only 4 then if we still keep subtracting it then is -4 which terminate the looping process). So the remainder becomes the GCD.

Finally, i implement these steps in a C++ program to determine the GCD :

#include <iostream>
using namespace std;

int gcd(int m, int n)
/* precondition: m>0 and n>0.  Let g=gcd(m,n). */
{ while( m > 0 )
{ /* invariant: gcd(m,n)=g */
if( n > m )
{ int t = m; m = n; n = t; } /* swap */
/* m >= n > 0 */
m -= n;
}
return n;
}

int main () {

int num1, num2, the_gcd;
cout << “Two integers : ” ;
cin >> num1 >> num2;
the_gcd = gcd(num1, num2);
cout << endl << ” The GCD of ” << num1 << ” and ” << num2
<< ” is ” << the_gcd;
return 0;
}

Have a good learning and lesson!! feel free to ask in this blog if you guys dont understand.

salam, fahmi