LebGeeks

A community for technology geeks in Lebanon.

You are not logged in.

#1 June 27 2015

O_Koles
Member

GCD homework help

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.

Offline

#2 June 27 2015

AliMJD
Member

Re: GCD homework help

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);
		}

Offline

Board footer