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:

  1. Is this C++ code equivalent to the Python code shown?
  2. Is this code considered idiomatic in C++ programming?
  3. 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?
 4  118  4
1 Jan 1970

Solution

 3

This is a summary of what @Jarod42 said in the comments, I was waiting for him to post an answer so I could accept it but since that didn't happen, here is the answer to my question.

  1. Yes, this code is equivalent to the Python code show above.
  2. No, this is not the idiomatic way of writting C++ code but seems like it would not bother many C++ developpers as it seems by the comments.
  3. For trivial types this can probably be optimized away but for non-trivial types, we have an extra copy when creating a tuple and we are relying on the compiler to make the optimizations.

He also pointed out that for my use case one can use the std::exchange from C++14. This is my refactored code after the comments.

std::int64_t inv_modulo(std::int64_t a, std::int64_t b) {
  std::int64_t old_s = 1, s = 0;
  std::int64_t old_t = 0, t = 1;

  while (a % b != 0) {
    auto div_result = std::div(a, b);
    old_s = std::exchange(s, old_s - div_result.quot * s);
    old_t = std::exchange(t, old_t - div_result.quot * t);
    a = std::exchange(b, div_result.rem);
  }
  return s;
}
2024-07-10
João Areias

Solution

 2

AFAIK, std::tie was originally designed for exactly similar kind of use; as the left side of an assignment, though later other useful cases might've showed up. The idiom is illustrated relativity well in the OP snippet:

  • structured binding for decoupling tuple-like values.
  • std::tie on the left side of assignment
  • std::tuple constructor(or std::make_tuple for older standard revisions) on the right side of assignment.

std::tie creates a temporary tuple of references to elements, who need to be assigned from another tuple. The main objectives of every program are functionally and readability. Optimization concerns only come after careful benchmarking.

2024-07-09
Red.Wave