Velocity Reviews - Computer Hardware Reviews

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

Reply
Thread Tools

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
}

 
Reply With Quote
 
 
 
 
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"
 
Reply With Quote
 
 
 
 
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
 
Reply With Quote
 
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

 
Reply With Quote
 
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
> }
>

 
Reply With Quote
 
 
 
Reply

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 Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Simple greatest common factor script fejky Python 2 11-29-2009 11:23 AM
greatest multiple algorithm Bronson C Programming 4 06-29-2007 02:25 PM
Greatest Common Divisor using Extended Euclid's Algorithm sdlt85@gmail.com C++ 2 05-30-2007 09:27 AM
Greatest Common Divisor using Extended Euclid's Algorithm sdlt85@gmail.com C Programming 0 05-30-2007 04:03 AM
4 bit divisor with flip-flop ? eric VHDL 15 02-05-2004 03:31 AM



Advertisments