




Greatest Common Divisor using Extended Euclid's Algorithm
Hi, Can someone help me with an idea on how to start writing a C++ code for generating greatest common divisor and the linear combination of two intergers represented as gcd(m, n)= mx + ny and adding them it will give us the greatest common divisor and I need to use the extended Euclidean algorithm. I already have the code for the greatest common divisor but I dont know how to do the linear combination. This is what I have: #include <iostream> #include <iomanip> using namespace std; void gcd(int, int); void extended_gcd(int, int, int, int); int main() { int m=0, n=0; cout<<"Welcome to the Greatest Common Divisor Program\n\n"; cout<<"Enter the first number: "; cin>>m; cout<<endl; cout<<"Enter the second number: "; cin>>n; cout<<endl; cout<<"gcd("<<m<<", "<<n<<") = "; gcd(m, n); return 0; }
void gcd(int m, int n) { int r, q, d; while (n!=0) { r = m % n; q = m / n; r = m  n * q; // I was thinking on put it on the stack // but I dont know how m = n; n = r; } d = m; cout<<d<<endl; //then pop the stack as d=rq*n
}
Hello, sdl @gmail.com wrote: > Hi, > Can someone help me with an idea on how to start writing a C++ code > for generating > greatest common divisor and the linear combination of two intergers > represented as gcd(m, n)= mx + ny and adding them it will give us the > greatest common divisor and I need to use the extended Euclidean > algorithm. > I already have the code for the greatest common divisor but I dont > know how to do the linear combination. It's not easy to find on your own, but it is easy to code. Use your favourite textbooks on computer algebra as a starting point, or start reading with the Wikipedia article, I think there are example implementations referenced easily adaptable to C++. http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm Bernd Strieder
sdl @gmail.com wrote: > Hi, > Can someone help me with an idea on how to start writing a C++ code > for generating > greatest common divisor and the linear combination of two intergers > represented as gcd(m, n)= mx + ny gcd(m, n)= mx + ny ??? It makes no sense to me. gcd( m, n ) is always going to be less than or equal to m or n. mx + ny will be larger than either of m or n. What exactly is it you are trying to do ?





