|
|
 |
 |
 |
 |
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=r-q*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.
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
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 ?
|
 |
 |
 |
 |
|
Add to del.icio.us |
Digg this |
Stumble it |
Powered by Megasolutions Inc