COME ON CODE ON

A blog about programming and more programming.

Binary GCD Algorithm

with 2 comments

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

Advertisements

Written by fR0DDY

February 26, 2009 at 12:08 PM

Posted in Maths, Programming

Tagged with , , ,

2 Responses

Subscribe to comments with RSS.

  1. Dude I got here while stumbling 😉

    Rohit Jaiswal

    November 28, 2010 at 2:35 AM

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

    prateekprshr

    September 16, 2015 at 12:14 AM


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: