extended euclid

[kakashi316]

Im writing a program involving extended euclid.
[

include <iostream>
//#include<fstream>
using namespace std; 

int gcd(int a, int b)
{
	if(b == 0)
	{
	        return a;
	}
	else
	{
		return gcd(b, a % b);
	}
}
int extended_gcd(int a,int b)
{
	int x;
	int y;
	if (a%b==0)
	{
        return (0, 1);
	}
	else
	{
        (x, y) = extended_gcd(b, a%b);
		return (y, x-(y*(a/b));
	}
}

int main()
{
     int a,b;
     //ofstream outf("f://output.txt",ios::out); 
     cout << "Input first number: ";
	 //outf<< "Input first number: ";
     cin >> a;
	 //outf << a<<endl;
     cout << "Input second number: ";
	 //outf<<"Input second number: ";
     cin >> b;
	 //outf<< b<<endl;
     
     cout << "Greatest common divisior (GCD) is " << gcd(a,b) << endl;
	 //outf<<"Greatest common divisior (GCD) is " << gcd(a,b) << endl;
	 cout<<"The extended Euclid is "<<extended_gcd(a,b)<<endl;
     system("pause");
	 return 0;
}

Im getting an error line 27:
f:\rsacrypto\rsacrypto\functions.cpp(27): error C2143: syntax error : missing ')' before ';'

If someone can give me a heads up as to were i screwed up i would appreciate it.

[Galik]

Read the error. It says you have a missing ')' on line 27.

Look at like 27 and count the parentheses.

[kakashi316]

ok,i got it to run.Im just not sure if my funtion in working properly.

#include <iostream>
//#include<fstream>
using namespace std; 

int gcd(int a, int b)
{
	if(b == 0)
	{
	        return a;
	}
	else
	{
		return gcd(b, a % b);
	}
}
int extended_gcd(int a,int b)
{
	int x;
	int y;
	if (a%b==0)
	{
        return (0, 1);
	}
	else
	{
        (x, y) = extended_gcd(b, a%b);
		return (y, x=(y*(a/b)));
	}
}

int main()
{
     int a,b;
     //ofstream outf("f://output.txt",ios::out); 
     cout << "Input first number: ";
	 //outf<< "Input first number: ";
     cin >> a;
	 //outf << a<<endl;
     cout << "Input second number: ";
	 //outf<<"Input second number: ";
     cin >> b;
	 //outf<< b<<endl;
     
     cout << "Greatest common divisior (GCD) is " << gcd(a,b) << endl;
	 //outf<<"Greatest common divisior (GCD) is " << gcd(a,b) << endl;
	 cout<<"The extended Euclid is "<<extended_gcd(a,b)<<endl;
     system("pause");
	 return 0;
}

if someone can go over it and see if i made a mistake implementing the function,id appreciate it.

[Bazzy]

You can't assign variables like that (x, y) = extended_gcd(b, a%b); ( nor return (y, x=(y*(a/b))); )
Instead of using ints use a std::pair<int> http://www.cplusplus.com/reference/std/utility/pair/

[jsmith]

Also, be very careful because both your gcd() and extended_gcd() functions require that a >= b. If a < b, they
will incorrectly report 0 (assuming you fix Bazzy's comment).

[ne555]

@jsmith: The gcd() is ok, if a<b then in the recursive call a>b.

[Duthomhas]

@ne555: The gcd() is not ok, if a<b then in the recursive b==0. Oops! mod != div

[ne555]

1 2 3 4 5 6

int gcd(int a, int b){ if(b == 0) return a; else return gcd(b, a % b); }

Desk test: gcd(12, 15); //a<b call gcd(15, 12%15) -> gcd(15, 12) //now a>b call gcd(12, 15%12) -> gcd(12, 3) call gcd(3, 12 % 3) -> gcd(3, 0) return 3;

am I missing something?

if a<b then a%b = a

so the function just swap the parameters.

[Duthomhas]

Nope. I missed something. (Whanged me upside the head...)