I have here a simple program to find the GCD - Greatest Common Divisor of 2 numbers using Euclidean algorithm. I guess that's the fastest way to compute GCD.

Here is the code:

I believe that the logic is correct. And i don't get any errors. But the output is always 0. (i.e., diff=0)

I have only ever used that algorithm in recursive methods.

John Eipe
Ranch Hand

Joined: May 23, 2008
Posts: 215

posted

0

So you mean I need to change this into a recursive function to make it work.

Isn't there any other way? I wonder why for loop doesn't work.

Peter Tellanaki
Greenhorn

Joined: Apr 27, 2009
Posts: 7

posted

0

oh my,
i really nedd sleep !
forget all i said. your program will work if both numbers positive. if one positive one negative infinit loop. if both negative 0 always.
the way you use Euclid you must make certain both numbers are >0. but this is ok since +- no effect on gcd. so just sub first
x = Math.max(x, y); y = Math.min(x, y); with fx x = max of absolute values of x and y.

Peter Tellanaki
Greenhorn

Joined: Apr 27, 2009
Posts: 7

posted

0

so for example

public class GCD {
public static void main(String[] args) throws IOException{
BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
int diff=0;
System.out.println("Enter num1: ");
int x = Integer.parseInt(read.readLine());
System.out.println("Enter num2: ");
int y = Integer.parseInt(read.readLine());
x = Math.max(abs(x), abs(y));
y = Math.min(abs(x), abs(y));
[deleted]

System.out.print("GCD of the nums :"+diff);

}
private static int abs( int arg) {
return arg > 0 ? arg : -arg;
}
}

note: bad style with the static abs, but just to quick fix )

Seems to work fine for me.
Tried it out for 121 and 1001.

Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 41851

31

posted

0

Peter Tellanaki, I am very sorry (please don't be annoyed with me), but I have felt obliged to pull rank and delete part of your submission. If you look on the Beginner's Forum start page, it says

We're all here to learn, so when responding to others, please focus on helping them discover their own solutions, instead of simply providing answers.

Simply providing the answer would prevent John Eipe from learning for himself.

How did you get it right? I don't think there are problems with negative numbers. As there are no cases of negative numbers coming in the code. As per the original post - we always take the greater and subtract the lesser one from it.

John Eipe
Ranch Hand

Joined: May 23, 2008
Posts: 215

posted

0

Great Rob,
that's were the problem lies. I just substituted that part with a swap code: