Results 1 to 7 of 7
  1. #1
    AlexGraal is online now Señor Member
    Join Date
    Jan 2014
    Posts
    161
    Rep Power
    0

    Default Efficient GCD calculation and "long" forloops

    Hi.


    My GCD testing:
    Java Code:
    public static long gcd(long a, long b) {
        if(b == 0) {
          return a;
        } else {
          return gcd(b, a % b);
        }
      }
    Is there a more efficient way?

    Also, what can I do to speed this forloop up?

    Java Code:
    for(long i = 1; i < 750000; i++) { dothis; }

  2. #2
    jim829 is online now Senior Member
    Join Date
    Jan 2013
    Location
    United States
    Posts
    3,388
    Rep Power
    5

    Default Re: Efficient GCD calculation and "long" forloops

    Yeah. Stay away from recursion because it isn't efficient. Just loop around Euclid's method until the modulus is 0. Then the preceding value is the GCD. And as an added benefit, if you want to calculate the LCM, just divide the product of a and b by the GCD. However, I can't say if that is efficient or not.

    For speeding up the for loop, use ints instead of longs. There are special byte codes for handing ints more efficiently. But you'll have to time it to see if it makes a difference.

    Regards,
    Jim
    The Java™ Tutorial | SSCCE | Java Naming Conventions
    Poor planning our your part does not constitute an emergency on my part.

  3. #3
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,348
    Blog Entries
    7
    Rep Power
    20

    Default Re: Efficient GCD calculation and "long" forloops

    Quote Originally Posted by jim829 View Post
    Yeah. Stay away from recursion because it isn't efficient.
    Ahem, maybe the Java implementation of handling recursion is less than efficient, but there's nothing wrong with recursion in itself (sic); functional programming languages that remove tail recursive calls make the original example as efficient as an iterative approach (I still wonder why Java doesn't remove tail recursion).

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  4. #4
    gimbal2 is online now Just a guy
    Join Date
    Jun 2013
    Location
    Netherlands
    Posts
    3,695
    Rep Power
    5

    Default Re: Efficient GCD calculation and "long" forloops

    Well primarily because Java isn't a living entity that can make decisions ;) ;) ;)

    Recursion has its uses and efficiency is a broad term - I rarely care about execution efficiency when programming in Java, because that makes -me- inefficient.
    "Syntactic sugar causes cancer of the semicolon." -- Alan Perlis

  5. #5
    jim829 is online now Senior Member
    Join Date
    Jan 2013
    Location
    United States
    Posts
    3,388
    Rep Power
    5

    Default Re: Efficient GCD calculation and "long" forloops

    Ok Jos, enlighten me. How can successive method calls and pushing stuff on the stack be more efficient than a straight iterative approach. Or am I mixing up the concept of recursion with what I presume is the way Java implements it?

    Regards,
    Jim
    The Java™ Tutorial | SSCCE | Java Naming Conventions
    Poor planning our your part does not constitute an emergency on my part.

  6. #6
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,348
    Blog Entries
    7
    Rep Power
    20

    Default Re: Efficient GCD calculation and "long" forloops

    Quote Originally Posted by jim829 View Post
    Ok Jos, enlighten me. How can successive method calls and pushing stuff on the stack be more efficient than a straight iterative approach. Or am I mixing up the concept of recursion with what I presume is the way Java implements it?
    It would be just as efficient as an iterative implementation if Java would've eliminated the tail recursion. The recursive call would just be a jump back to the start of the body of the method (just as a 'while' statement would be).
    cenosillicaphobia: the fear for an empty beer glass

  7. #7
    AlexGraal is online now Señor Member
    Join Date
    Jan 2014
    Posts
    161
    Rep Power
    0

    Default Re: Efficient GCD calculation and "long" forloops

    Actually, I'd like to know now. I've seen you posting around about being able to do stuff with recursion as efficiently if not more efficiently with iteration.

    How would you iteratively write a program that returns if a certain number can be created using a given set of other numbers?

    Aka, given 100, 90, 110, 80, 2, can you create 95?


    Recursively:
    Java Code:
      public static void main ( String[] args ) {
        double[] hold = {100,90,2};
        System.out.println(canMake(0, hold, 95, 0));
      }
      public static boolean canMake ( int start, double[] nums, double target, double tot ) {
        if(tot == target) return true;
        if(start >= nums.length) return false;
        return (canMake(start + 1, nums, target, tot + nums[start]) || canMake(start + 1, nums, target, tot - nums[start]) || 
    canMake(start + 1, nums, target, tot * nums[start]) || canMake(start + 1, nums, target, tot / nums[start]) || canMake(start + 1, nums, target, tot));
      }
    Can you actually improve the running time with simply iteration?

Similar Threads

  1. Replies: 5
    Last Post: 03-14-2013, 11:39 AM
  2. Replies: 0
    Last Post: 12-07-2012, 08:29 AM
  3. Replies: 2
    Last Post: 11-30-2008, 03:24 PM
  4. Replies: 1
    Last Post: 10-20-2008, 07:35 AM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •