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

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

Hello,

sdl@gmail.com wrote:
> 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.

It's not easy to find on your own, but it is easy to code.

Use your favourite textbooks on computer algebra as a starting point, or
start reading with the Wikipedia article, I think there are example
implementations referenced easily adaptable to C++.

http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm

Bernd Strieder

sdl@gmail.com wrote:
> 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

gcd(m, n)= mx + ny ???

It makes no sense to me.

gcd( m, n ) is always going to be less than or equal to m or n.

mx + ny will be larger than either of m or n.

What exactly is it you are trying to do ?

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