Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

euclid's extended algorithm C ++

Tags:

c++

algorithm

I'm having an issue with Euclid's Extended Algorithm. (ax+by=gcd(a,b)) I'm trying to determine both the GCD and x and y. The GCD isn't a problem but using the loop method something is going wrong with x and y. Normally one number comes up as 0 and the other is an abnormally large negative number. Code follows:

#include <iostream>

using namespace std;

main ()
{
    int a,b,q,x,lastx,y,lasty,temp,temp1,temp2,temp3;
    cout << "Please input a" << endl;
    cin >> a; 
    cout << "Please input b" << endl;
    cin >> b;
    if (b>a) {//we switch them
        temp=a; a=b; b=temp;
    }
    //begin function
    x=0;
    y=1;
    lastx=1;
    lasty=0;
    while (b!=0) {
        q= a/b;
        temp1= a%b;
        a=b;
        b=temp1;

        temp2=x-q*x;
        x=lastx-q*x;
        lastx=temp2;

        temp3=y-q*y;
        y=lasty-q*y;
        lasty=temp3;
    }

    cout << "gcd" << a << endl;
    cout << "x=" << lastx << endl;
    cout << "y=" << lasty << endl;
    return 0;
}
like image 405
user1735851 Avatar asked Oct 10 '12 18:10

user1735851


People also ask

What is Euclid's algorithm in C?

Euclidean algorithms (Basic and Extended) Write an iterative O(Log y) function for pow(x, y) Write program to calculate pow(x, n) Modular Exponentiation (Power in Modular Arithmetic) Modular exponentiation (Recursive)

What is Euclids algorithm formula?

The Euclidean Algorithm for finding GCD(A,B) is as follows: If A = 0 then GCD(A,B)=B, since the GCD(0,B)=B, and we can stop. If B = 0 then GCD(A,B)=A, since the GCD(A,0)=A, and we can stop. Write A in quotient remainder form (A = B⋅Q + R)

What is the difference between Euclidean and extended Euclidean algorithm?

Given two integers a and b: the Euclidean Algorithm computes GCD(a,b) the Extended Euclidean Algorithm gives out 2 integers x and y such that ax+by=GCD(a,b); mainly used when GCD(a,b)=1.


2 Answers

Although the question has been asked a long time ago, but the answer will help someone who were finding C++ implementation of extended euclidean algorithm.

Here is a recursive C++ implementation:

int xGCD(int a, int b, int &x, int &y) {
    if(b == 0) {
       x = 1;
       y = 0;
       return a;
    }

    int x1, y1, gcd = xGCD(b, a % b, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;
    return gcd;
}

Example with code:

#include <iostream>

int main()
{
   int a = 99, b = 78, x, y, gcd;

   if(a < b) std::swap(a, b);

   gcd = xGCD(a, b, x, y);
   std::cout << "GCD: " << gcd << ", x = " << x << ", y = " << y << std::endl;

   return 0;
}

Input:

a = 99, b =78

Output:

GCD: 3, x = -11, y = 14

like image 154
maruf Avatar answered Oct 18 '22 12:10

maruf


Two of your assignments are wrong they should be:

    temp2 = x;
    x=lastx-q*x;
    lastx = temp2;

    temp3 = y;
    y = lasty-q*y;
    lasty=temp3;

Example output with the above fixes:

Please input a
54
Please input b
24
gcd6
x=1
y=-2
like image 44
GWW Avatar answered Oct 18 '22 14:10

GWW