Greatest Common Divisor using Extended Euclid's Algorithm

[sdlt85]

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
}

[Keith Thompson]

sd****@gmail.com writes:

Can someone help me with an idea on how to start writing a C++ code

[snip]

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) ks***@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"

[Eric Sosman]

sd****@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
es*****@acm-dot-org.invalid

[sdlt85]

On May 29, 11:44 pm, Eric Sosman <[e-mail]:

[e-mail] 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
[e-mail]

Thanks

[Martin Ambuhl]

sd****@gmail.com wrote:

Hi,
Can someone help me with an idea on how to start writing a C++ code

step 1: learn that C++ is a different language from C. Posts about C++
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
}