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

• September 24th, 2013, 01:07 PM
EDale
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

Code java:

```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.
• September 24th, 2013, 01:36 PM
GregBrannon
Re: GCD Algorithm... could you help explain what kind of code I need to write?
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.
• September 24th, 2013, 06:31 PM
EDale
Re: GCD Algorithm... could you help explain what kind of code I need to write?
Thanks so much! I'll post my solution when I figure it out!
• September 24th, 2013, 10:11 PM
EDale
Re: GCD Algorithm... could you help explain what kind of code I need to write?
Here's what I got!

Code java:

```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!
• September 24th, 2013, 11:13 PM
GregBrannon
Re: GCD Algorithm... could you help explain what kind of code I need to write?
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:
Code java:

``` // 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!