#include
#include
using namespace std;
//Source: extendedeuclideanalgorithm.com
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
//Warning: can't handle b=0. See extendedeuclideanalgorithm.com/code for a version that can
/* Calculating the greatest common divisor
using the Euclidean Algorithm (non-recursive).
(Source: extendedeuclideanalgorithm.com/code) */
int gcd_iterative(int a, int b){
//Set default values for the quotient and the remainder
int q = 0;
int r = 1;
/*In each iteration of the loop below, we
calculate the new quotient, remainder, a and b.
r decreases, so we stop when r = 0*/
while(r > 0){
//The calculations
q = floor(a/b);
r = a - q * b;
//The values for the next iteration
a = b;
b = (r > 0)? r : b;
}
return abs(b);
}
/* Calculating the greatest common divisor
using the Euclidean Algorithm (non-recursive)
(Source: extendedeuclideanalgorithm.com/code) */
int gcd_iterative2(int a, int b){
//Set default values for the quotient and the remainder
int q = 0;
int r = 1;
/*In each iteration of the loop below, we
calculate the new quotient, remainder, a and b.
r decreases, so we stop when r = 0*/
while(b > 0){
//The calculations
q = floor(a/b);
r = a - q * b;
//The values for the next iteration
a = b;
b = r;
}
return abs(a);
}
/* Calculating the greatest common divisor
using the Euclidean Algorithm (recursive)
(Source: extendedeuclideanalgorithm.com/code) */
int gcd(int a, int b){
if(b == 0){
return abs(a);
}
int q = floor(a/b);
int r = a - q * b;
return (r == 0)? abs(b) : gcd(b, r);
}
//Global variables used by the Extended Euclidean Algorithm
int s = 0;
int t = 0;
//Warning: this version can't handle b=0. See extendedeuclideanalgorithm.com/code for a version that can.
/* Calculates the gcd and Bézout coefficients,
using the Extended Euclidean Algorithm (non-recursive).
(Source: extendedeuclideanalgorithm.com/code) */
int xgcd_iterative(int a, int b){
//Set default values for the quotient, remainder,
//s-variables and t-variables
int q = 0;
int r = 1;
int s1 = 1;
int s2 = 0;
int s3 = 1;
int t1 = 0;
int t2 = 1;
int t3 = 0;
/*In each iteration of the loop below, we
calculate the new quotient, remainder, a, b,
and the new s-variables and t-variables.
r decreases, so we stop when r = 0*/
while(r > 0){
//The calculations
q = floor(a/b);
r = a - q * b;
s3 = s1 - q * s2;
t3 = t1 - q * t2;
/* The values for the next iteration,
(but only if there is a next iteration)*/
if(r > 0){
a = b;
b = r;
s1 = s2;
s2 = s3;
t1 = t2;
t2 = t3;
}
}
s = s2;
t = t2;
return abs(b);
}
//Can handle b=0
/* Calculates the gcd and Bézout coefficients,
using the Extended Euclidean Algorithm (non-recursive).
(Source: extendedeuclideanalgorithm.com/code) */
int xgcd_iterative2(int a, int b){
//Set default values for the quotient, remainder,
//s-values and t-values
int q = 0;
int r = 1;
int s1 = 1;
int s2 = 0;
int s3 = 1;
int t1 = 0;
int t2 = 1;
int t3 = 0;
/*In each iteration of the loop below, we
calculate the new quotient, remainder, a, b,
and the new s-values and t-values.
r decreases, so we stop when r = 0*/
while(b > 0){
//The calculations
q = floor(a/b);
r = a - q * b;
s3 = s1 - q * s2;
t3 = t1 - q * t2;
a = b;
s1 = s2;
t1 = t2;
b = r;
s2 = s3;
t2 = t3;
}
s = s1;
t = t1;
return abs(a);
}
/* Calculates the gcd and Bézout coefficients,
using the Extended Euclidean Algorithm (recursive).
(Source: extendedeuclideanalgorithm.com/code) */
int xgcd(int a, int b, int s1 = 1, int s2 = 0, int t1 = 0, int t2 = 1){
if(b == 0){
s = 1; t = 0;
return abs(a);
}
int q = floor(a/b);
int r = a - q * b;
int s3 = s1 - q * s2;
int t3 = t1 - q * t2;
s = s2;
t = t2;
return (r == 0)? abs(b) : xgcd(b, r, s2, s3, t2, t3);
}
/* Calculates the multiplicative inverse of a number b mod n,
using the Extended Euclidean Algorithm. If b does not have a
multiplicative inverse mod n, then throw an exception.
(Source: extendedeuclideanalgorithm.com/code) */
int multinv(int b, int n){
if(xgcd(n, b) == 1){
//t is a global variable that is assigned a value by xgcd
return (t + n) % n;
}
else{
throw -1;
}
}
int main(int argc, char** argv) {
//Use your own values for a and b
int a = 20;
int b = 15;
cout << gcd(a, b);
//Euclidean Algorithm:
//see the output of gcd(a, b)
cout << "Euclidean Algorithm:" << endl;
cout << "The gcd of " << a << " and " << b << " is " << gcd(a, b) << endl;
//-------------------------------------------------------------
/*Extended Euclidean Algorithm:
see the output of xgcd(a,b) and Bezout coefficients
And verify that they are correct.*/
int my_gcd = xgcd(a, b); //xgcd will set global variables s and t
int verification = abs(s*a+t*b);
cout << "Extended Euclidean Algorithm:" << endl;
cout << "The gcd of " << a << " and " << b << " is " << my_gcd << endl;
cout << "And the Bezout coefficients: s=" << s << " and t=" << t << "." << endl;
cout << "And " << s << " * " << a << " + " << t << " * " << b << " = " << verification << endl;
if(my_gcd == verification){
cout << "So as we expect, s*a+t*b is equal to the gcd we found." << endl;
}
else{
cout << "Something went wrong" << endl;
}
//#------------------------------------------------------------
b = 15;
int n = 10;
/*Multiplicative Inverse:
Try to compute the multiplicative inverse of b mod n.
If that succeeds, verify that it's correct.
If it doesn't succeed, show the error raised by the function.*/
try {
cout << multinv(b, n) << endl;
}
catch (int n) {
cout << "Error: there is no multiplicative inverse for the given numbers" << endl;
}
return 0;
}