## Binary GCD Algorithm

Most of us know that to find the GCD of two numbers, Euclid Algorithm is the best algorithm. But thanks to **Josef Stein**, there is the Binary GCD Algorithm which is touch faster than the Euclid’s Algorithm.

The Euclids Algorithm implemented is :

long long gcd(long long a, long long b) { if(a==0) return(b); return(gcd(b%a, a)); }

The Binary GCD Algorithm as given in the The Art of Computer Programming written by D.E.Knuth is as follows :

Given positive integers u and v, this algorithm finds their greatest common divisor. A1. [Find power of 2.] Set k←0, and then repeatedly set k← k + 1, u ← u/2,v ← v/2, zero or more times until u and v are not both even. A2. [Initialize.] (Now the original values of u and v have been divided by 2^k,and at least one of their present values is odd.) If u is odd, set t ← -v, and go to A4. Otherwise set t ← u. A3. [Halve t.] (At this point, t is even, and nonzero.) Set t ← t/2. A4. [Is t even?] If t is even, go back to A3. A5. [Reset max(u, v).] If t > 0, set u ← t; otherwise set v← -t. (The larger of u and v has been replaced by |t|, except perhaps during the first time this step is performed.) A6. [Subtract.] Set t ← u-v. If t != 0, go back to A3. Otherwise the algorithm terminates with u* 2^k as the output.

Implementation in C++ would look something like this :

int binarygcd(int u,int v)

{

int k=0,t=0,i;

while (!(u&1) && !(v&1))

{

k++;

u>>=1;

v>>=1;

}

if (u&1)

t=u;

else

t=-v;

do

{

while (!(t&1))

t>>=1;

if (t>0)

u=t;

else

v=-t;

t=u-v;

}while (t);

for (i=0;i

Dude I got here while stumbling 😉

Rohit JaiswalNovember 28, 2010 at 2:35 AM

Nice post dude thank you, needless to say AOCP rocks.

prateekprshrSeptember 16, 2015 at 12:14 AM