pow_mod, inverse の速度

ベンチマークコード

適当．g++ -O2．標準入力は適当に10とか入れてる．

const ll MOD = 1000000009;

const int N = 2000000;

int main() {
  int a;
  scanf("%d", &a);

  ll t = a;
  for (int k = 1; k <= N; ++k) {
    t = inverse(t, MOD) * k % MOD;
  }
  printf("%lld\n", t);

  return 0;
}

今までのやつ

駆け出しだった頃の僕が，適当に bmerry か誰かのやつを参考にして書いた．中で再帰している上にいちいち丁寧に正にするために % を 2 回もとってて遅そう．（でもマイナスが帰るとそれが原因のバグをつくりそうで恐ろしいからなあ）

inline ll mod(ll a, ll m) { return (a % m + m) % m; }

ll inverse(ll a, ll m) {
  if ((a = mod(a, m)) == 1) return 1;
  return mod((1 - m * inverse(m % a, a)) / a, m);
}

~/contests/tmp% time ./a.out <<< 10 [14:10:35]
249011238
./a.out <<< 10 2.84s user 0.01s system 99% cpu 2.870 total
~/contests/tmp% time ./a.out <<< 10 [14:10:39]
249011238
./a.out <<< 10 2.85s user 0.00s system 99% cpu 2.870 total
~/contests/tmp% time ./a.out <<< 10 [14:10:43]
249011238
./a.out <<< 10 2.83s user 0.02s system 99% cpu 2.868 total

inline

再帰関数だからあんま意味分からんと思うが一応 inverse に inline つけてみた．

~/contests/tmp% g++ -O2 inverse.cpp [14:11:39]
~/contests/tmp% time ./a.out <<< 10 [14:11:41]
249011238
./a.out <<< 10 2.75s user 0.00s system 99% cpu 2.763 total
~/contests/tmp% time ./a.out <<< 10 [14:11:44]
249011238
./a.out <<< 10 2.75s user 0.00s system 99% cpu 2.762 total
~/contests/tmp% time ./a.out <<< 10 [14:11:49]
249011238
./a.out <<< 10 2.75s user 0.00s system 100% cpu 2.748 total

ちょっぴりはやくなったｗ

pow_mod １

今まで使っていた pow_mod を使う．これも再帰していて丁寧に mod を呼んでいて見るからに遅そうである．

inline ll mod(ll a, ll m) { return (a % m + m) % m; }

ll pow_mod(ll a, ll k, ll m) {
  if (k == 0) return 1;
  ll t = pow_mod(a, k / 2, m);
  return mod(mod(t * t, m) * (k % 2 ? a : 1), m);
}

inline ll inverse(ll a, ll m) {
  return pow_mod(a, m - 2, m);
}

~/contests/tmp% time ./a.out <<< 10 [14:13:19]
249011238
./a.out <<< 10 3.39s user 0.00s system 99% cpu 3.407 total
~/contests/tmp% time ./a.out <<< 10 [14:13:23]
249011238
./a.out <<< 10 3.39s user 0.00s system 99% cpu 3.407 total
~/contests/tmp% time ./a.out <<< 10 [14:13:28]
249011238
./a.out <<< 10 3.37s user 0.02s system 99% cpu 3.411 total

遅くなったｗ

pow_mod ２

pow_mod を高速そうな実装にしてみる．

inline ll pow_mod(ll a, ll k, ll m) {
  ll r = 1;
  for (; k > 0; k >>= 1) {
    if (k & 1) (r *= a) %= m;
    (a *= a) %= m;
  }
  return r;
}

~/contests/tmp% time ./a.out <<< 10 [14:16:27]
249011238
./a.out <<< 10 0.45s user 0.01s system 99% cpu 0.463 total
~/contests/tmp% time ./a.out <<< 10 [14:16:28]
249011238
./a.out <<< 10 0.47s user 0.00s system 100% cpu 0.468 total
~/contests/tmp% time ./a.out <<< 10 [14:16:31]
249011238
./a.out <<< 10 0.45s user 0.01s system 99% cpu 0.463 total

むっちゃはやくなったｗ

少し予想はしていたが，今までのはやはり爆遅だった