Efficient GCD calculation and "long" forloops

Hi.

My GCD testing:

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?

Code:

`for(long i = 1; i < 750000; i++) { dothis; }`

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

Re: Efficient GCD calculation and "long" forloops

Quote:

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

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.

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

Re: Efficient GCD calculation and "long" forloops

Quote:

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

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:

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?