Welcome to the Java Programming Forums

The professional, friendly Java community. 21,500 members and growing!

The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.

>> REGISTER NOW TO START POSTING

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

1. ## 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.  Reply With Quote

3. ## 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.  Reply With Quote

4. ## 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!  Reply With Quote

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

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!  Reply With Quote

6. ## 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:
```        //  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!  Reply With Quote 