• Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

GCD calculation using Euclidean algorithm fails

 
John Eipe
Ranch Hand
Posts: 215
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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!
 
pete stein
Bartender
Posts: 1561
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
This is an important question, but I'm not sure it's a GUI question. I'd like to ask the moderators to move this question to a more appropriate forum.
 
John Eipe
Ranch Hand
Posts: 215
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks Pete. You are right; it's not a GUI question. This got posted there by mistake. How do I raise a request to moderators to move this post?
 
Maneesh Godbole
Saloon Keeper
Posts: 11312
16
Android Eclipse IDE Google Web Toolkit Java Mac Ubuntu
 
Peter Tellanaki
Greenhorn
Posts: 7
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
hello,

you say
fo(; x-y !=0;){
diff=x-y
....
}
and then you print out diff. so in your for loop when you exit it diff is always zero.

[Edited: This is wrong. Please below see ]
 
Peter Tellanaki
Greenhorn
Posts: 7
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
sorry ! my wrong answer.
perhaps because of scope ?
you have global diff = 0. and [x and y] diff in for loop perhaps only local ?
 
Campbell Ritchie
Sheriff
Posts: 51343
86
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I have only ever used that algorithm in recursive methods.
 
John Eipe
Ranch Hand
Posts: 215
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 7
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 7
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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]
 
Ulf Dittmer
Rancher
Posts: 42969
73
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
This is where the problem is:

x = Math.max(x, y);
y = Math.min(x, y);
 
Sridhar Santhanakrishnan
Ranch Hand
Posts: 317
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
@john,

Seems to work fine for me.
Tried it out for 121 and 1001.
 
Campbell Ritchie
Sheriff
Posts: 51343
86
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Rob Spoor
Sheriff
Pie
Posts: 20745
68
Chrome Eclipse IDE Java Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
John Eipe
Ranch Hand
Posts: 215
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Sridhar,

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
Posts: 215
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Great Rob,
that's were the problem lies. I just substituted that part with a swap code:


and it works perfectly fine.

Thank you All.
 
Rob Spoor
Sheriff
Pie
Posts: 20745
68
Chrome Eclipse IDE Java Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
 
Campbell Ritchie
Sheriff
Posts: 51343
86
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Lots of people get confused about swapping like that.
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic