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;
}
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)
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)
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.
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
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
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With