Greatest Common Divisor problem

[tejas2991]

this is my gcd prog..

#include<iostre am>
using namespace std;
int GCD(int ,int );
void main()
{
int x,y;
cout<<"Plz enter the two numbers : ";
cin>>x>>y;
cout<<"The GCD("<<x<<","<< y<<") = " << GCD(x,y)<<endl;
}
int GCD(int x,int y)
{
if(y>x)return GCD(y,x);
if(x==y)return x;
if(x%y==0)retur n y;
return GCD(x,x-y);

}


if i enter numbers like 13 17..the prog gets stuck..so now how to solve that error????

[donbock]

@tejas2991
Let's walk through the sequence of recursive GCD calls:

GCD(13,17)    ; operator input
GCD(17,13)    ; because (y>x)
GCD(17,4)     ; fall-through
GCD(17,13)    ; fall-through
...           ; uh-oh!

Can you express your GCD algorithm mathematically?

[JosAH]

I moved the two posts above to a separate thread; the question has nothing to do with the thread it came from.

kind regards,

Jos (moderator)

[tejas2991]

hey i found the solution!!!!

instead of all those if case :

if(y==0)
return y;

return gcd(y,x%y);

[donbock]

@tejas2991
That can't be right -- that function returns "0" for all values of x and y.

[whodgson]

int GCD(int x,int y) 
{ 
    if(y>x) return GCD(y,x); 
    if(x==y) return x; 
    if(x%y==0) return y; 
    return GCD(x,x-y); 
} 

long gcd(long m,long n)
{
     if(m>n)swap(m,n);
     assert(n>0);
     while(n>0)
     {
      long r=m%n;
      m=n;
      n=r;
     }
     return m;
}     

This returns 1 as it should
Line 3 in the quoted function looks wrong -- but I don`t know why.