Modulo Multiplication

たまに大きな数同士のかけ算をオーバーフローさせずに計算し、その modulo が取りたい時があります。 多倍長演算を実装すればいいわけですが、大変面倒なので何か簡単な方法はないかなーと調べていたらありました。

C++ で書くと以下のようになります。

#include <cstdio>
#include <cinttypes>

/**
 * if b is even then
 *   a * b = 2 * a * (b / 2)
 * otherwise
 *   a * b = a + a * (b - 1)
 *
 * (a * b) % mod = (2a * b / 2) % mod
 *               = (a + a + a + ...(b times)... + a) % mod
 */
std::int64_t modpow(std::int64_t a, std::int64_t b, std::int64_t m)
{
  std::int32_t r = 0;
  a %= m;

  while (b) {
    if (b & 1) {
      r = (r + a) % m;
    }

    a = (2 * a) % m;
    b >>= 1;
  }

  return r;
}

int main( void )
{
  using namespace std;

  printf("%lu\n", modpow(32933923828, 219009238, 1 << 31));
  
  return 0;
}

基本的な原理はコードのコメントにも記載していますが、

という感じです。

同じ考え方を使って、$x^{n} \bmod m$ を効率良く計算する方法もあり、以下のようにします。

std::int32_t mmod(std::int32_t x, std::int32_t n, std::int32_t m)
{
  if (n == 0) {
    return 1;
  }

  if (n % 2 ==0) {
    auto t = mmod(x, n / 2, m);
    return (t * t) % m;
  }

  return (mmod(x, n - 1, m) * x) % m;
}

これらの計算手法はどうもプログラミングコンテスト界隈では必須の知識なようで、日本語では繰り返し二乗法、英語では exponentiation by squaring と呼ぶらしいです。

Comments

comments powered by Disqus