




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=rq*n
}
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=rq*n
}
sdl @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) k@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"
sdl @gmail.com 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 esos@acmdotorg.invalid
On May 29, 11:44 pm, Eric Sosman <esos@acmdotorg.invalid> wrote:
> sdl @gmail.com 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 > esos@acmdotorg.invalid
Thanks
sdl @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 <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=rq*n > }





