Threaded Mode | Linear Mode

***drdebcol*** · 12-25-2009, 06:50 AM

This is an interesting algorithm for finding the greatest common divisor. I already explained Euclid Algorithm here :
http://www.pro9ramming.com/the-biggest-gcd-t-596.html
But now i am going to use binary GCD algorithm.
More about that you have here :
http://en.wikipedia.org/wiki/Binary_GCD_algorithm
And i have solution in C++ :

Code:

# include <iostream>

# include <cstdio>

using namespace std;

 int gcd(int u,int v)

{

     int s;

     if (u == 0 || v == 0)

       return u | v;

     for (s = 0; ((u | v) & 1) == 0; ++s) {

         u >>= 1;

         v >>= 1;

     }

     while ((u & 1) == 0)

       u >>= 1;

     do {

         while ((v & 1) == 0) 

           v >>= 1;

         if (u < v) {

             v -= u;

         } else {

             int diff = u - v;

             u = v;

             v = diff;

         }

         v >>= 1;

     } while (v != 0);

     return u<<s;

 }

int main()

{

    int a,b;

    cin>>a;

    cin>>b;

    cout<<gcd(a,b)<<endl;

    system("pause");

}