eea.cpp

// clang++ eea.cpp -std=c++17 -o eea -O3
// ./eea <num1> <num2> <num3> <num4> ...

#include <cstdint>
#include <cstdlib>
#include <utility>  // std::swap

struct result {
  std::int64_t s;
  std::int64_t t;
  std::int64_t gcd;
};

// Used so that we can use structured bindings nicely
// (i.e. in a ring buffer kind of way).
template <typename T>
struct h {
  T& a0;
  T& a1;
  T& a2;

  h(T* arr, std::uint32_t offset)
      : a0{arr[offset % 3]},
        a1{arr[(offset + 2) % 3]},
        a2{arr[(offset + 1) % 3]} {}
};

template <typename T>
h(T*, std::uint32_t)->h<T>;

result eea(std::int64_t r0, std::int64_t r1) noexcept {
  if (r0 <= r1) {
    std::swap(r0, r1);
  }

  std::int64_t r[3] = {r0, r1, 0};
  std::int64_t s[3] = {1, 0, 0};
  std::int64_t t[3] = {0, 1, 0};

  // Can't declare it in the for loop
  std::uint32_t i = 2;
  for (; r[(i + 2) % 3] != 0; ++i) {
    // This might be oddly named.
    // x0 = x_i, x1 = x_{i-1}, x2 = x_{i-2}
    auto[r0, r1, r2] = h{r, i};
    auto[s0, s1, s2] = h{s, i};
    auto[t0, t1, t2] = h{t, i};

    r0 = r2 % r1;

    const auto q = (r2 - r0) / r1;

    s0 = s2 - q * s1;
    t0 = t2 - q * t1;
  }

  return {s[(i + 1) % 3], t[(i + 1) % 3], r[(i + 1) % 3]};
}

#include <iostream>

int main(int argc, char** argv) {
  argc -= 1;
  if (argc % 2) {
    std::cout << "Usage: \"" << argv[0] << "\" r0 r1 r2 r3 ... rn\n"
              << "The algorithm will be run on (r0, r1), (r2, r3), ..."
              << std::endl;
    return 0;
  }

  // just used to output the index after "r"
  const auto old_argc = argc;

  for (char **p = argv + 1; argc; argc -= 2, p += 2) {
    const auto[s, t, gcd] = eea(std::atoll(p[0]), std::atoll(p[1]));
    std::cout << 'r' << (old_argc - argc) / 2 << " = " << p[0] << " -- r"
              << (old_argc - argc) / 2 + 1 << " = " << p[1]
              << "\n\tgcd = " << gcd << "\n\ts = " << s << "\n\tt = " << t
              << '\n';
  }

  std::cout << std::flush;

  return 0;
}