Euclid's Algorithm

[mineja101473]

Can someone help me with my C++ program. For some reason I Compile the program, but when I run it I have problems. I type in the first integer, then I type in the second integer and the program times out (ie it disappears). I start over and it does the same thing.

[CODE=cpp]#include <iostream>

using namespace std ;

int main()
{

int x, y, temp, remainder;

// read in the two integers

cout << endl ;
cout << "Enter the first number (integer) : " ;
cin >> x ;
cout << "Enter the second number (integer) : " ;
cin >> y ;

// echo inputs

cout << "Input numbers are: " << x << " , " << y << endl;

{// exchange values of x and y
if(x == y)
{
return x;
}
else if(x < y)
{
y = y - x ;
}
else
{
x = x - y ;
}
}

/* At this point we will always have x >= y */

//Initialize remainder.

while (x > 0)
{
temp = x % y;
x = y;
y = temp;
}

// display the result
cout << endl ;
cout << "The GCD is: " << y << endl ;

system("PAUSE") ;
return (0); // terminate with success
}[/CODE]

[Ganon11]

I can see 2 things wrong.

1) If x == y, then you return x - but you're returning it inside main(). main() is expecting a 0 to be returned, signaling that everything worked as expected, no errors. When you return x, any non-zero value is going to signal that there was an error somewhere along the line. Maybe you should simply ignore this case?

2) Your next two if...branches don't work like your comment says they should. The first half is correct - if y is greater than x, subtract x from y. But if x is greater than y, you subtract y from x, making x smaller than y. So in the case that x is initially greater than y, your comment is false, because afterwards y > x.

Fixing these may or may not fix your hangtime problem - I'll try and look through your code again.

[JosAH]

2) Your next two if...branches don't work like your comment says they should. The first half is correct - if y is greater than x, subtract x from y. But if x is greater than y, you subtract y from x, making x smaller than y. So in the case that x is initially greater than y, your comment is false, because afterwards y > x.

Not necessarily; a counter example: x == 21, y == 3. After the subtraction:
x == 18, y == 3 which still makes x > y.

The entire program is just totally wrong. The classic GCD algorithm can be found
anywhere on Google so I leave it at that.

kind regards,

Jos

[Ganon11]

Not necessarily; a counter example: x == 21, y == 3. After the subtraction:
x == 18, y == 3 which still makes x > y.

The entire program is just totally wrong. The classic GCD algorithm can be found
anywhere on Google so I leave it at that.

kind regards,

Jos

In which case, the first if...branch is also incorrect, using the same values you had, but reversed (x==3, y==21).

[JosAH]

In which case, the first if...branch is also incorrect, using the same values you had, but reversed (x==3, y==21).

Yep, but I was too lazy to show two examples; as I wrote: the entire algoritm
as shown is completely wrong; no need to dig into the (incorrect) details more
than necessary, i.e. one counter example is more than enough.

kind regards,

Jos