|
|
 |
 |
 |
 |
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
}
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
}
sdl @gmail.com writes: > Can someone help me with an idea on how to start writing a C++ code
This is comp.lang.c. comp.lang.c++ is down the hall, just past the
water cooler, second door on the left.
--
Keith Thompson (The_Other_Keith) k@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
sdl @gmail.com wrote: > Hi, > Can someone help me with an idea on how to start writing a C++ code > [...]
... but you've chosen a strange place to look for
him or her. This is a newsgroup devoted to C, not to
C++, and (not to put too fine a point on it) some of
the devotees of C think C++ is the work of the Devil
and will have nothing to do with it -- they may or may
not be right, but if they shun C++ they are not likely
to be willing (or able) to offer you much help.
I suggest you seek assistance in one or more of
the following newsgroups:
comp.crypto.burn.before.reading
alt.religion.kibology
comp.fortran.fossils
rec.swedish.chef.bork.bork.bork
comp.lang.c++
alt.tin.foil.helmets
Choose whichever seems most likely to be helpful, and
try your question there.
--
Eric Sosman
esos@acm-dot-org.invalid
On May 29, 11:44 pm, Eric Sosman <esos@acm-dot-org.invalid> wrote:
> sdl @gmail.com wrote: > > Hi, > > Can someone help me with an idea on how to start writing a C++ code > > [...] > Yes! Someone can help you!
> ... but you've chosen a strange place to look for
> him or her. This is a newsgroup devoted to C, not to
> C++, and (not to put too fine a point on it) some of
> the devotees of C think C++ is the work of the Devil
> and will have nothing to do with it -- they may or may
> not be right, but if they shun C++ they are not likely
> to be willing (or able) to offer you much help.
> I suggest you seek assistance in one or more of
> the following newsgroups:
> comp.crypto.burn.before.reading
> alt.religion.kibology
> comp.fortran.fossils
> rec.swedish.chef.bork.bork.bork
> comp.lang.c++
> alt.tin.foil.helmets
> Choose whichever seems most likely to be helpful, and
> try your question there.
> --
> Eric Sosman
> esos@acm-dot-org.invalid
sdl @gmail.com wrote: > Hi, > Can someone help me with an idea on how to start writing a C++ code
are not topical in <news:comp.lang.c>. The C++ newsgroup is
<news:comp.lang.c++>, but your post is about algorithms independent of
any language, so is not topical there either.
> 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.
The above makes no sense.
1) If you "have the code for the greatest common divisor" then you are done.
2) You _don't_ have the code for the greatest common divisor.
Here is a version of you code which
a) is legal C so is topical here
b) has a working (if not best) gcd() function.
Now, what was your question?
#include <stdio.h>
int gcd(int, int); /* notice return type */
int main(void)
{
int m = 0, n = 0;
puts("Welcome to the Greatest Common Divisor Program\n\n"
"Enter the first number: ");
scanf("%d", &m);
puts("\nEnter the second number: ");
scanf("%d", &n);
printf("gcd(%d,%d) =%d\n", m, n, gcd(m, n));
return 0;
}
int gcd(int m, int n)
{
if (!m || !n) return 0;
if (m < 0) return gcd(-m,n);
if (n < 0) return gcd(m,-n);
if (m < n) return gcd(n,m);
if (m%n) return gcd(n, m%n);
return n;
} > 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
> }
|
 |
 |
 |
 |
|
Add to del.icio.us |
Digg this |
Stumble it |
Powered by Megasolutions Inc