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

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,706
    James Dennett
    Aug 14, 2005
  2. Replies:
    4
    Views:
    1,318
    Martin Ambuhl
    May 30, 2007
  3. Replies:
    2
    Views:
    755
    Gianni Mariani
    May 30, 2007
  4. Bronson

    greatest multiple algorithm

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

Share This Page