GCD calculation using Euclidean algorithm fails
John Eipe
Ranch Hand
Posts: 215
posted 7 years ago
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.csrepository.info
pete stein
Bartender
Posts: 1561
John Eipe
Ranch Hand
Posts: 215
Peter Tellanaki
Greenhorn
Posts: 7
Peter Tellanaki
Greenhorn
Posts: 7
Campbell Ritchie
Marshal
Posts: 52664
122
John Eipe
Ranch Hand
Posts: 215
Peter Tellanaki
Greenhorn
Posts: 7
posted 7 years ago
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 7 years ago
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: 42970
73
Sridhar Santhanakrishnan
Ranch Hand
Posts: 317
Campbell Ritchie
Marshal
Posts: 52664
122
posted 7 years ago
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 7 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.
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 7 years ago
Of course you can change that to the following, eliminating the empty body of the ifstatement:
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
Anderson gave himself the promotion. So I gave myself this tiny ad:
the new thread boost feature brings a LOT of attention to your favorite threads
https://coderanch.com/t/674455/ThreadBoostfeature
