# Greatest Common Divisor using Extended Euclid's Algorithm

Discussion in 'C Programming' started by sdlt85@gmail.com, May 30, 2007.

1. ### Guest

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, 2007

2. ### Keith ThompsonGuest

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) <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"

Keith Thompson, May 30, 2007

3. ### Eric SosmanGuest

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
lid

Eric Sosman, May 30, 2007
4. ### Guest

On May 29, 11:44 pm, Eric Sosman <> wrote:
> 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
>

Thanks

, May 30, 2007
5. ### Martin AmbuhlGuest

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

Martin Ambuhl, May 30, 2007