473,379 Members | 1,330 Online

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

May 30 '07 #1
4 13658
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"
May 30 '07 #2
sd****@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:

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

--
Eric Sosman
es*****@acm-dot-org.invalid
May 30 '07 #3
On May 29, 11:44 pm, Eric Sosman <esos...@acm-dot-org.invalidwrote:
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:

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

--
Eric Sosman
esos...@acm-dot-org.invalid
Thanks

May 30 '07 #4
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
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.

#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
}
May 30 '07 #5

This thread has been closed and replies have been disabled. Please start a new discussion.