@Neha: Although some have suggested Euclid's Algorithm without
condition, and some have expressed disgust that you would even ask the
question, it actually is worth discussing. If division is expensive
compared to logical operations, such as in a microcontroller that does
not have a hardware divide instruction, then a binary GCD algorithm
along the following lines may be better. I know, because I have
implemented gcd in this case.
int gcd( int a, int b) // a > 0 and b > 0 is assumed
{
int i, k=0;
i = a | b;
while( i & 1 )
{
i >>= 1;
++k;
}
a >>= k;
b >>= k;
while( a & 1 ) a >>= 1;
while( b & 1 ) b >>= 1;
while( 1 )
{
if( a > b )
{
a -= b;
while( a & 1 ) a >>= 1;
}
else
{
b -= a;
if( b == 0 ) return a<<k;
while( b & 1 ) b >>= 1;
}
}
}
This algorithm, which avoids division, is based on the following
properties of GCD:
1. gcd(a,b) = gcd(b,a)
2. gcd(a,0) = a
3. if a and b are even, gcd(a,b) = 2*gcd(a/2,b/2)
4. if a is odd and b is even, gcd(a,b) = gcd(a,b/2)
5. if a and b are both odd and a >= b, then gcd(a,b) = gcd(a-b,b) and
a-b is even.
Dave
On Sep 10, 10:24 am, Neha Singh <[email protected]> wrote:
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
