# GCD calculation using Euclidean algorithm fails

John Eipe

Ranch Hand

Posts: 215

posted 6 years ago

- 0

Hi,

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)

Please HELP!

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)

Please HELP!

www.cs-repository.info

pete stein

Bartender

Posts: 1561

John Eipe

Ranch Hand

Posts: 215

Peter Tellanaki

Greenhorn

Posts: 7

Peter Tellanaki

Greenhorn

Posts: 7

Campbell Ritchie

Sheriff

Posts: 47216

52

John Eipe

Ranch Hand

Posts: 215

Peter Tellanaki

Greenhorn

Posts: 7

posted 6 years ago

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

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

Posts: 7

posted 6 years ago

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

[edit]Delete solution. CR[/edit]

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 )

[edit]Delete solution. CR[/edit]

Ulf Dittmer

Rancher

Posts: 42966

73

Sridhar Santhanakrishnan

Ranch Hand

Posts: 317

Campbell Ritchie

Sheriff

Posts: 47216

52

posted 6 years ago

- 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

Simply providing the answer would prevent John Eipe from learning for himself.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.

posted 6 years ago

Exactly. You overwrite x with the maximum of x and y. Now if y is larger than x, x and y will end up having the same value.

- 0

Ulf Dittmer wrote:This is where the problem is:

x = Math.max(x, y);

y = Math.min(x, y);

Exactly. You overwrite x with the maximum of x and y. Now if y is larger than x, x and y will end up having the same value.

SCJP 1.4 - SCJP 6 - SCWCD 5 - OCEEJBD 6 - OCEJPAD 6

How To Ask Questions How To Answer Questions

John Eipe

Ranch Hand

Posts: 215

John Eipe

Ranch Hand

Posts: 215

posted 6 years ago

- 0

Of course you can change that to the following, eliminating the empty body of the if-statement:

And I think Ulf would like some gratitude as well

And I think Ulf would like some gratitude as well

SCJP 1.4 - SCJP 6 - SCWCD 5 - OCEEJBD 6 - OCEJPAD 6

How To Ask Questions How To Answer Questions

With a little knowledge, a cast iron skillet is non-stick and lasts a lifetime. |