Garner algorithm
(Mylib/Number/garner.cpp)

• View this file on GitHub
• Last update: 2021-04-23 23:44:44+09:00

Operations

Requirements

Notes

Problems

References

Depends on

• Mod inverse (Mylib/Number/Mod/mod_inv.cpp)

Code

#pragma once
#include <cassert>
#include <vector>
#include "Mylib/Number/Mod/mod_inv.cpp"

namespace haar_lib {
  int64_t garner_algorithm(std::vector<int64_t> r, std::vector<int64_t> m, const int64_t mod) {
    assert(r.size() == m.size());
    m.push_back(mod);

    int n = r.size();
    std::vector<int64_t> coeffs(n + 1, 1);
    std::vector<int64_t> constants(n + 1, 0);

    for (int k = 0; k < n; ++k) {
      int64_t t = ((r[k] - constants[k] + m[k]) % m[k] * mod_inv(coeffs[k], m[k])) % m[k];
      for (int i = k + 1; i < n + 1; ++i) {
        (constants[i] += t * coeffs[i] % m[i]) %= m[i];
        (coeffs[i] *= m[k]) %= m[i];
      }
    }

    return constants.back();
  }
}  // namespace haar_lib

#line 2 "Mylib/Number/garner.cpp"
#include <cassert>
#include <vector>
#line 2 "Mylib/Number/Mod/mod_inv.cpp"
#include <cstdint>
#include <utility>

namespace haar_lib {
  constexpr int64_t mod_inv(int64_t a, int64_t m) {
    int64_t b = m, u = 1, v = 0;

    while (b) {
      int64_t t = a / b;
      a -= t * b;
      a = a ^ b;
      b = a ^ b;
      a = a ^ b;

      u -= t * v;
      u = u ^ v;
      v = u ^ v;
      u = u ^ v;
    }

    u %= m;
    if (u < 0) u += m;

    return u;
  }
}  // namespace haar_lib
#line 5 "Mylib/Number/garner.cpp"

namespace haar_lib {
  int64_t garner_algorithm(std::vector<int64_t> r, std::vector<int64_t> m, const int64_t mod) {
    assert(r.size() == m.size());
    m.push_back(mod);

    int n = r.size();
    std::vector<int64_t> coeffs(n + 1, 1);
    std::vector<int64_t> constants(n + 1, 0);

    for (int k = 0; k < n; ++k) {
      int64_t t = ((r[k] - constants[k] + m[k]) % m[k] * mod_inv(coeffs[k], m[k])) % m[k];
      for (int i = k + 1; i < n + 1; ++i) {
        (constants[i] += t * coeffs[i] % m[i]) %= m[i];
        (coeffs[i] *= m[k]) %= m[i];
      }
    }

    return constants.back();
  }
}  // namespace haar_lib

Back to top page