# Thread: Efficient GCD calculation and "long" forloops

1. Señor Member
Join Date
Jan 2014
Posts
184
Rep Power
0

## 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. Senior Member
Join Date
Jan 2013
Location
Northern Virginia, United States
Posts
5,644
Rep Power
9

## 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

3. ## Re: Efficient GCD calculation and "long" forloops

Originally Posted by jim829
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

4. Just a guy
Join Date
Jun 2013
Location
Netherlands
Posts
5,114
Rep Power
9

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

5. Senior Member
Join Date
Jan 2013
Location
Northern Virginia, United States
Posts
5,644
Rep Power
9

## 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

6. ## Re: Efficient GCD calculation and "long" forloops

Originally Posted by jim829
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).

7. Señor Member
Join Date
Jan 2014
Posts
184
Rep Power
0

## 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?

#### Posting Permissions

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