# COME ON CODE ON

A blog about programming and more programming.

## 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

Written by fR0DDY

February 26, 2009 at 12:08 PM

Posted in Maths, Programming

Tagged with , , ,