Thread: GCD Algorithm... could you help explain what kind of code I need to write?

I have this homework question and I'm not 100% sure what it's asking. Could you break it down for me or write the skeleton code so I can get a better grasp of it?

Write an alternative gcd algorithm, based on the following observations (arrange A > B) .

a. gcd(A, B) = 2*gcd(A/2, B/2) if A and B are both even
b. gcd(A, B) = gcd(A/2, B) if A is even and B is odd
c. gcd(A, B) = gcd(A, B/2) if A is odd and B is even
d. gcd(A, B) = gcd( (A+B)/2, (A-B)/2) if A and B are both odd

public static long gcd ( long a , long b ) {
      if (a < b) return gcd ( b , a ) ;
     // a >= b 
     if (b == 0) return a ;
     …   // complete the code here using the logic given above in a, b, c and d

How would I write something like this? I don't even understand the piece of code that is given.

It's a cookbook approach to finding the GCD of A and B that uses recursion. Below the line,

// complete the code here . . .

the assignment asks you to code the logic for a, b, c, and d that are described above. For example, for (a), there will be an if statement that determines that both A and B are equal (use the modulus operator) and then the body of the if statement will calculate the gcd as:

2 * gcd( A/2, B/2 );

You'll do the same for b, c, and d.

I haven't seen this approach before, so I'll code it myself when I get home this afternoon. Let me know how your coding is going, and we'll compare results.

Thanks so much! I'll post my solution when I figure it out!

Here's what I got!

public static long gcd ( long a , long b ) {
      if (a < b) return gcd ( b , a ) ;
     // a >= b 
     if (b == 0) 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%2==1 && b%2==1) {
	return gcd((a+b)/2, (a-b)/2);
}
}

What did you get? Should I put a condition in if none are met?

--- Update ---

sorry about the shitty syntax, my computer wont let me edit it!

Have you tested it?

Is a return required if none are met? Yes, even if it's never used. At the end I added

return 1L;

but it could have been 0 or most any number, because it'll never happen. Even so, the compiler will require it so that every possible path through the method returns a value.

After adding a default return, the important parts of yours look very similar to mine, and testing yours I get correct answers, so I think you did great.

On these assignments with the requirements stated so specifically, I add them right to my code as comments:

        //  a. A and B are both even: gcd(A, B) = 2*gcd(A/2, B/2)
        if ( a % 2 == 0 && b % 2 == 0 )
        {
            return 2 * ( gcd( a / 2, b / 2 ) );
        }

In fact, I add the requirement as comments first and then write the code. It's hard to mess up that way.

Good job with such a light nudge in the right direction!