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
    #1
    1. Advertising

  2. 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
    #2
    1. Advertising

  3. Eric Sosman Guest

    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
    lid
     
    Eric Sosman, May 30, 2007
    #3
  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
    > > [...]

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


    Thanks
     
    , May 30, 2007
    #4
  5. 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
    > }
    >
     
    Martin Ambuhl, May 30, 2007
    #5
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Erik the Red

    Euclid's Algorithm in Python?

    Erik the Red, Aug 5, 2005, in forum: Python
    Replies:
    12
    Views:
    1,750
    James Dennett
    Aug 14, 2005
  2. Replies:
    0
    Views:
    510
  3. Replies:
    2
    Views:
    773
    Gianni Mariani
    May 30, 2007
  4. Bronson

    greatest multiple algorithm

    Bronson, Jun 28, 2007, in forum: C Programming
    Replies:
    4
    Views:
    427
    Thad Smith
    Jun 29, 2007
  5. fejky
    Replies:
    2
    Views:
    360
    fejky
    Nov 29, 2009
Loading...

Share This Page