Binary exponentiation
(Mylib/Number/pow.cpp)

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

Operations

Requirements

Notes

Problems

References

Required by

• Range multiply / Range product (Mylib/AlgebraicStructure/MonoidAction/multiply_product.cpp)

Code

#pragma once
#include <cassert>
#include <cstdint>

namespace haar_lib {
  template <typename Monoid, typename value_type = typename Monoid::value_type>
  value_type pow(value_type a, int64_t p) {
    assert(p >= 0);
    const Monoid M;
    auto ret = M();

    while (p > 0) {
      if (p & 1) ret = M(ret, a);
      a = M(a, a);
      p >>= 1;
    }

    return ret;
  }
}  // namespace haar_lib

#line 2 "Mylib/Number/pow.cpp"
#include <cassert>
#include <cstdint>

namespace haar_lib {
  template <typename Monoid, typename value_type = typename Monoid::value_type>
  value_type pow(value_type a, int64_t p) {
    assert(p >= 0);
    const Monoid M;
    auto ret = M();

    while (p > 0) {
      if (p & 1) ret = M(ret, a);
      a = M(a, a);
      p >>= 1;
    }

    return ret;
  }
}  // namespace haar_lib

Back to top page