Question
Idiomatic ways of using tuples and std::tie
I am trying to implement the modular multiplicative inverse using the extended Euclidean algorithm in C++. In Python, the code for this is concise and idiomatic, using tuple unpacking:
def inv_modulo(a: int, b: int) -> int:
_s, s = 1, 0
_t, t = 0, 1
while a % b != 0:
q, r = divmod(a, b)
_s, s = s, _s - q * s
_t, t = t, _t - q * t
a, b = b, r
return s
I want to replicate this behavior in C++ and have written the following code:
long long inv_modulo(long long a, long long b) {
long long old_s = 1, s = 0;
long long old_t = 0, t = 1;
while (a % b != 0) {
auto [q, r] = std::lldiv(a, b);
std::tie(old_s, s) = std::make_tuple(s, old_s - q * s);
std::tie(old_t, t) = std::make_tuple(t, old_t - q * t);
std::tie(a, b) = std::make_tuple(b, r);
}
return s;
}
I have three specific questions about this implementation:
- Is this C++ code equivalent to the Python code shown?
- Is this code considered idiomatic in C++ programming?
- Is there a performance penalty for writing the code this way compared another approach, for example using temporary variables for the intermediate steps of the computation?