Extended euclidean algorithm for negative numbers

Question

How to correctly calculate the coefficients of the Bezout ratio for the case of negative numbers in the implementation of the extended euclidean algorithm? Here is my code:

#include <iostream>
#include <cmath>
#include <tuple>
 
using namespace std;
 
tuple<int, int, int> xgcd(int a, int b, int s1 = 1, int s2 = 0, int t1 = 0, int t2 = 1) {
    if (b == 0) {
        return {abs(a), s1, t1};
    }
    int q = a / b;
    return xgcd(b, a - q * b, s2, s1 - q * s2, t2, t1 - q * t2);
}
 
int main(double argc, char ** argv) {
    tuple<int, int, int> result = xgcd(-10, -15);
    cout << get<0>(result) << " " << get<1>(result) << " " << get<2>(result) << endl;
 
    return 0;
};

In the presented case (-10, -15), the GCD is calculated correctly, but the Bezout coefficients require inverting the sign. What is the right way to deal with them? Thank you in advance!)

not related to the question, but the first parameter of main should be an int — Neil Butterworth
– Neil Butterworth, Commented Oct 17, 2022 at 13:55
Please do not use std::tuple (or pair) for code which is not a template, just declare a struct with proper field names. What is more readable and maintainable: get<0>(result) or result.x? — Marek R
– Marek R, Commented Oct 17, 2022 at 14:19

Dave Bowman · Accepted Answer · 2022-10-20 11:46:13Z

I figured out the problem. The solution is: replace a and b with their modules at the very beginning of the algorithm. But then the Bezout's coefficients will be found incorrectly. Let, for example, a < 0, and b > 0. Then after changing the sign of a, the resulting Bezout's identity will look like this:

gcd(a, b) = s(-a) + tb (in terms of -a and b)

or

gcd(a, b) = -sa + tb (in terms of a and b).

In general , for a and b arbitrary signs , this will be written

gcd(a, b) = sgn(a)sa + sgn(b)tb.

Thus, if we change the sign of a, then we must change the sign of s. Similarly, if we change the sign of b, then we must change the sign of t. Thus, the algorithm in recursive form will be written as follows:

    tuple<int, int, int> xgcd(int a, int b, int sign_a = 0, int sign_b = 0, int s1 = 1, int s2 = 0, int t1 = 0, int t2 = 1) {
        if (!sign_a) {
            sign_a = a < 0 ? -1 : 1;
        }
        if (!sign_b) {
            sign_b = b < 0 ? -1 : 1;
        }
        a = abs(a);
        b = abs(b);
        if (b == 0) {
            return {a, sign_a * s1, sign_b * t1};
        }
        int q = a / b;
        return xgcd(b, a - q * b, sign_a, sign_b, s2, s1 - q * s2, t2, t1 - q * t2);
    }

Collectives™ on Stack Overflow

Extended euclidean algorithm for negative numbers

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related