You are not logged in.
Pages: 1
hey guys, i've been having problems with a exercise in my homework, its a greatest common divisor method that is recursive, but the instructor said to use the binary way, i think its called like that , where if
-A is even and B is even then GCD(A/2,B/2)
-A is odd and B is even then GCD(A,B/2)
-A is even and B is odd then GCD(A/2,B)
and here is my code :
public static long gcd( long a , long b ) {
//assert ( a % 2 == 0 || b % 2 == 0 );
if ( a == b ) {
return a;
}
else if ( a % 2 == 0 && b % 2 == 0 ) return 2 * gcd( a / 2 , b / 2 );
else if ( a % 2 == 0 && b % 2 == 1 ) return gcd( a / 2 , b );
else if ( a % 2 == 1 && b % 2 == 0 ) return gcd( a / 2 , b );
//assert ( a % 2 == 1 && b % 2 == 1 );
else {
if ( a == 0 ) return b;
if ( b == 0 ) return a;
if ( a > b ) return gcd( b , a % b );
return gcd( a , b % a );
}
}
my problem is that its giving StackOverFlowException at the third else if.
what do you guys think is the problem.
Hi O_Koles,
The problem in your code is that you are combining both the Euclidean algorithm and the binary one for GCD Recursive problem.
public static long gcd( long a , long b ) {
//assert ( a % 2 == 0 || b % 2 == 0 );
if ( a == b ) {
return a;
}
else if ( a % 2 == 0 && b % 2 == 0 ) return 2 * gcd( a / 2 , b / 2 );
else if ( a % 2 == 0 && b % 2 == 1 ) return gcd( a / 2 , b );
else if ( a % 2 == 1 && b % 2 == 0 ) return gcd( a / 2 , b ); // and this must be return gcd( a , b /2);
//assert ( a % 2 == 1 && b % 2 == 1 );
else {
if ( a == 0 ) return b; // this piece of code is alone the Euclidean algorithim
if ( b == 0 ) return a; // and should be replaced by the binary one. ( The Case
if ( a > b ) return gcd( b , a % b ); // where both "a" and "b" are odd.) **below is the solution**
return gcd( a , b % a ); //
}
}
Binary Algorithm :
public static long gcd( long a , long b ) {
if ( a == 0 ) return b;
if ( b == 0 ) return a;
if ( a == b ) return a;
if ( a % 2 == 0 && b % 2 == 0 ) return 2 * gcd( a / 2 , b / 2 );
if ( a % 2 == 0 && b % 2 == 1 ) return gcd( a / 2 , b );
if ( a % 2 == 1 && b % 2 == 0 ) return gcd( a , b / 2 );
if ( a > b ) return gcd((a - b)/2, b);
return gcd((b - a)/2, a);
}
Euclidean algorithm:
public static long gcd(long a, long b){
if(a == 0) return b;
if(b == 0) return a;
if(a > b) return gcd(b, a % b);
return gcd(a, b % a);
}
Pages: 1