Home     |     .Net Programming    |     cSharp Home    |     Sql Server Home    |     Javascript / Client Side Development     |     Ajax Programming

Ruby on Rails Development     |     Perl Programming     |     C Programming Language     |     C++ Programming     |     IT Jobs

Python Programming Language     |     Laptop Suggestions?    |     TCL Scripting     |     Fortran Programming     |     Scheme Programming Language


 
 
Cervo Technologies
The Right Source to Outsource

MS Dynamics CRM 3.0

C Programming Language

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

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

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@acm-dot-org.invalid

On May 29, 11:44 pm, Eric Sosman <esos@acm-dot-org.invalid> wrote:

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;

Add to del.icio.us | Digg this | Stumble it | Powered by Megasolutions Inc