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


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 5 of 5

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

  1. #1
    Member
    Join Date
    Mar 2013
    Posts
    58
    Thanks
    3
    Thanked 0 Times in 0 Posts

    Default 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.


  2. #2
    Super Moderator
    Join Date
    Jun 2013
    Location
    So. Maryland, USA
    Posts
    5,520
    My Mood
    Mellow
    Thanks
    215
    Thanked 698 Times in 680 Posts

    Default 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.

  3. #3
    Member
    Join Date
    Mar 2013
    Posts
    58
    Thanks
    3
    Thanked 0 Times in 0 Posts

    Default 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!

  4. #4
    Member
    Join Date
    Mar 2013
    Posts
    58
    Thanks
    3
    Thanked 0 Times in 0 Posts

    Default 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!

  5. #5
    Super Moderator
    Join Date
    Jun 2013
    Location
    So. Maryland, USA
    Posts
    5,520
    My Mood
    Mellow
    Thanks
    215
    Thanked 698 Times in 680 Posts

    Default 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!

Similar Threads

  1. Replies: 1
    Last Post: September 9th, 2013, 11:26 AM
  2. need help with lehmer's gcd algorithm code
    By mirjamkolar in forum What's Wrong With My Code?
    Replies: 1
    Last Post: April 17th, 2013, 04:05 AM
  3. someone please be kind enough demonstrate a code like this......
    By willc86 in forum What's Wrong With My Code?
    Replies: 3
    Last Post: January 23rd, 2013, 06:32 AM
  4. Replies: 1
    Last Post: September 8th, 2012, 04:32 AM
  5. How to Write pos(part of speech) tagging algorithm?
    By Dinesh_here in forum Algorithms & Recursion
    Replies: 2
    Last Post: October 4th, 2011, 12:40 PM

Tags for this Thread