Replying to my own posting: I messed up the while statements. The code
should be
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;
}
}
}
On Sep 10, 11:50 am, Dave <[email protected]> wrote:
> @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:
>
>
>
> - Hide quoted text -
>
> - Show quoted text -
--
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.
