Extended Euclidean Algorithm in modern and readable C++

In Python the Extended Euclidean Algorithm (egcd) could be written as follows:

def egcd(a, b):
if b == 0:
return (a, 1, 0)
else:
(d, tmp, s) = egcd(b, a%b)
return (d, s, tmp - (a//b) * s)


I want to write a native and modern C++ version of the egcd. This is what I have so far:

template>
constexpr std::tuple egcd(A a, B b) {
  static_assert(std::is_integral::value, "arguments to egcd are integers");
  static_assert(std::is_integral::value, "arguments to egcd are integers");

  if (b == 0) {
    return std::make_tuple(a, 1, 0);
  } else {
    auto triple = egcd(b, a%b);
    return std::make_tuple(std::get(triple), std::get(triple), std::get(triple) - (a/b) * std::get(triple))
  }
}

As you can see using `` makes the code very long and hard (compare with the Python version..) to read.

Any suggestions to make this code more readable?

The code is rather tiny so there isn't much to say, but I still have a couple of remarks:

-
Since you're using C++17, you can take advantage of variable templates to simplify your static assertions a bit:

static_assert(std::is_integral_v, "arguments to egcd are integers");
static_assert(std::is_integral_v, "arguments to egcd are integers");

-
The LWG issues 2733 and 2759 highlight the fact that any possibly cv-qualified bool satisfies the std::is_integral trait, but the GCD and LCM operations don't make much sense for boolean types. Consequently, the extended operations don't make much sense for boolean types eithers. You could add the following static assertions to make it clear:

static_assert(not std::is_same_v, bool>, "arguments to egcd are not booleans");
static_assert(not std::is_same_v, bool>, "arguments to egcd are not booleans");

-
Since you're always computing both a / b and a % b, you can compute std::div instead which computes both at once and returns a structure with quot and rem members. Actually, the algorithm used to compute the remainder of a and b also computes the quotient of a and b, so functions like std::div exist in several programming languages so that users can take advantage of it instead of discarding a computed value and computing it again.

-
They're not widely available at the moment, but if you intend to keep returning an std::tuple, a C++17 decomposition declaration would probably make your code more readable by providing explicit names instead of the opaque std::get:

if (b == 0) {
    return std::make_tuple(a, 1, 0);
} else {
    auto divmod = std::div(a, b);
    auto [gcd, bezout_x, bezout_y] = egcd(b, divmod.rem);
    return std::make_tuple(gcd, bezout_y, bezout_x - divmod.quot * bezout_y)
}

StackExchange Code Review Q#139301, answer score: 6