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]

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.

 

[Eric Sosman]

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.

 

[sdlt85]

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.

Thanks

 

[Martin Ambuhl]

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 < The C++ newsgroup is

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;
}