Velocity Reviews > Greatest Common Divisor using Extended Euclid's Algorithm

# Greatest Common Divisor using Extended Euclid's Algorithm

sdlt85@gmail.com
Guest
Posts: n/a

 05-30-2007
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
Guest
Posts: n/a

 05-30-2007
http://www.velocityreviews.com/forums/(E-Mail Removed) 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) (E-Mail Removed) <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
Guest
Posts: n/a

 05-30-2007
(E-Mail Removed) 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 Removed)lid

sdlt85@gmail.com
Guest
Posts: n/a

 05-30-2007
On May 29, 11:44 pm, Eric Sosman <(E-Mail Removed)> wrote:
> (E-Mail Removed) 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 Removed)

Thanks

Martin Ambuhl
Guest
Posts: n/a

 05-30-2007
(E-Mail Removed) 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
> }
>

 Thread Tools

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is On HTML code is OffTrackbacks are On Pingbacks are On Refbacks are Off Forum Rules

 Similar Threads Thread Thread Starter Forum Replies Last Post fejky Python 2 11-29-2009 11:23 AM Bronson C Programming 4 06-29-2007 02:25 PM sdlt85@gmail.com C++ 2 05-30-2007 09:27 AM sdlt85@gmail.com C Programming 0 05-30-2007 04:03 AM eric VHDL 15 02-05-2004 03:31 AM

Advertisments