$b^n$ under a given monoid, and std::pow(b, n) extended for my library (tools/pow.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2024-08-31 13:46:12+09:00
• Include: #include "tools/pow.hpp"

(1)

template <typename M, typename E>
typename M::T pow(typename M::T b, E n);

template <typename T, typename E>
T pow(T b, E n);

It returns $b^n$ under a given monoid $M$. If $M$ is not given, tools::monoid::multiplies<T> will be used.

Constraints

• std::is_integral_v<E> is true.
• $n \geq 0$

Time Complexity

• $O(\log n)$ if M::op(b, b) takes $O(1)$ time

License

• CC0

Author

• anqooqie

(2)

template <typename T, typename E>
T pow(T b, E n);

If std::pow(b, n) is available, it returns std::pow(b, n).

tools::pow(b, n) will be extended by other header files in my library. For example, tools::pow(tools::quaternion<T>, T) gets available if you include tools/quaternion.hpp.

Constraints

• std::is_integral_v<E> is false.
• See the standard or the explanation of the corresponding header file.

Time Complexity

• See the standard or the explanation of the corresponding header file.

License

• CC0

Author

• anqooqie

Depends on

• std::gcd(m, n) extended for my library (tools/gcd.hpp)
• Check whether T is a monoid (tools/is_monoid.hpp)
• Typical monoids (tools/monoid.hpp)
• $x^2$ under a given monoid (tools/square.hpp)

Required by

• $\left\lceil x^\frac{1}{k} \right\rceil$ (tools/ceil_kth_root.hpp)
• tools/detail/rolling_hash.hpp
• $\left\lfloor x^\frac{1}{k} \right\rfloor$ (tools/floor_kth_root.hpp)
• $\mathbb{Z} / (2^{61} - 1) \mathbb{Z}$ (tools/modint_for_rolling_hash.hpp)
• $\mathrm{ord}(x)$ for $x \in (\mathbb{Z}/p\mathbb{Z})^\times$ (tools/ord_mod.hpp)
• Quaternion (tools/quaternion.hpp)
• Rolling hash (tools/rolling_hash.hpp)
• $x \uparrow\uparrow y \pmod{M}$ (tools/tetration_mod.hpp)
• Euler's totient function (tools/totient.hpp)

Verified with

• tests/ceil_kth_root.test.cpp
• tests/floor_kth_root.test.cpp
• tests/fps/exp_other_mods.test.cpp
• tests/fps/log_other_mods.test.cpp
• tests/fps/pow_other_mods.test.cpp
• tests/has_mod.test.cpp
• tests/ord_mod/count.test.cpp
• tests/ord_mod/query.test.cpp
• tests/permutation.test.cpp
• tests/quaternion/angle_axis.test.cpp
• tests/quaternion/dice_rotations.test.cpp
• tests/quaternion/look_rotation.test.cpp
• tests/quaternion/slerp.test.cpp
• tests/rolling_hash.test.cpp
• tests/tetration_mod.test.cpp
• tests/totient.test.cpp

Code

#ifndef TOOLS_POW_H
#define TOOLS_POW_H

#include <type_traits>
#include <cassert>
#include <cmath>
#include "tools/monoid.hpp"
#include "tools/square.hpp"

namespace tools {

  template <typename M, typename E>
  ::std::enable_if_t<::std::is_integral_v<E>, typename M::T> pow(const typename M::T& base, const E exponent) {
    assert(exponent >= 0);
    return exponent == 0
      ? M::e()
      : exponent % 2 == 0
        ? ::tools::square<M>(::tools::pow<M>(base, exponent / 2))
        : M::op(::tools::pow<M>(base, exponent - 1), base);
  }

  template <typename T, typename E>
  ::std::enable_if_t<::std::is_integral_v<E>, T> pow(const T& base, const E exponent) {
    assert(exponent >= 0);
    return ::tools::pow<::tools::monoid::multiplies<T>>(base, exponent);
  }

  template <typename T, typename E>
  auto pow(const T base, const E exponent) -> ::std::enable_if_t<!::std::is_integral_v<E>, decltype(::std::pow(base, exponent))> {
    return ::std::pow(base, exponent);
  }
}

#endif

#line 1 "tools/pow.hpp"



#include <type_traits>
#include <cassert>
#include <cmath>
#line 1 "tools/monoid.hpp"



#line 5 "tools/monoid.hpp"
#include <algorithm>
#include <limits>
#line 1 "tools/gcd.hpp"



#line 5 "tools/gcd.hpp"
#include <numeric>

namespace tools {
  template <typename M, typename N>
  constexpr ::std::common_type_t<M, N> gcd(const M m, const N n) {
    return ::std::gcd(m, n);
  }
}


#line 9 "tools/monoid.hpp"

namespace tools {
  namespace monoid {
    template <typename M, M ...dummy>
    struct max;

    template <typename M>
    struct max<M> {
      static_assert(::std::is_arithmetic_v<M>, "M must be a built-in arithmetic type.");

      using T = M;
      static T op(const T lhs, const T rhs) {
        return ::std::max(lhs, rhs);
      }
      static T e() {
        if constexpr (::std::is_integral_v<M>) {
          return ::std::numeric_limits<M>::min();
        } else {
          return -::std::numeric_limits<M>::infinity();
        }
      }
    };

    template <typename M, M E>
    struct max<M, E> {
      static_assert(::std::is_integral_v<M>, "M must be a built-in integral type.");

      using T = M;
      static T op(const T lhs, const T rhs) {
        assert(E <= lhs);
        assert(E <= rhs);
        return ::std::max(lhs, rhs);
      }
      static T e() {
        return E;
      }
    };

    template <typename M, M ...dummy>
    struct min;

    template <typename M>
    struct min<M> {
      static_assert(::std::is_arithmetic_v<M>, "M must be a built-in arithmetic type.");

      using T = M;
      static T op(const T lhs, const T rhs) {
        return ::std::min(lhs, rhs);
      }
      static T e() {
        if constexpr (::std::is_integral_v<M>) {
          return ::std::numeric_limits<M>::max();
        } else {
          return ::std::numeric_limits<M>::infinity();
        }
      }
    };

    template <typename M, M E>
    struct min<M, E> {
      static_assert(::std::is_integral_v<M>, "M must be a built-in integral type.");

      using T = M;
      static T op(const T lhs, const T rhs) {
        assert(lhs <= E);
        assert(rhs <= E);
        return ::std::min(lhs, rhs);
      }
      static T e() {
        return E;
      }
    };

    template <typename M>
    struct multiplies {
    private:
      using VR = ::std::conditional_t<::std::is_arithmetic_v<M>, const M, const M&>;

    public:
      using T = M;
      static T op(VR lhs, VR rhs) {
        return lhs * rhs;
      }
      static T e() {
        return T(1);
      }
    };

    template <>
    struct multiplies<bool> {
      using T = bool;
      static T op(const bool lhs, const bool rhs) {
        return lhs && rhs;
      }
      static T e() {
        return true;
      }
    };

    template <typename M>
    struct gcd {
    private:
      static_assert(!::std::is_arithmetic_v<M> || (::std::is_integral_v<M> && !::std::is_same_v<M, bool>), "If M is a built-in arithmetic type, it must be integral except for bool.");
      using VR = ::std::conditional_t<::std::is_arithmetic_v<M>, const M, const M&>;

    public:
      using T = M;
      static T op(VR lhs, VR rhs) {
        return ::tools::gcd(lhs, rhs);
      }
      static T e() {
        return T(0);
      }
    };

    template <typename M, M E>
    struct update {
      static_assert(::std::is_integral_v<M>, "M must be a built-in integral type.");

      using T = M;
      static T op(const T lhs, const T rhs) {
        return lhs == E ? rhs : lhs;
      }
      static T e() {
        return E;
      }
    };
  }
}


#line 1 "tools/square.hpp"



#line 1 "tools/is_monoid.hpp"



#line 5 "tools/is_monoid.hpp"
#include <utility>

namespace tools {

  template <typename M, typename = void>
  struct is_monoid : ::std::false_type {};

  template <typename M>
  struct is_monoid<M, ::std::enable_if_t<
    ::std::is_same_v<typename M::T, decltype(M::op(::std::declval<typename M::T>(), ::std::declval<typename M::T>()))> &&
    ::std::is_same_v<typename M::T, decltype(M::e())>
  , void>> : ::std::true_type {};

  template <typename M>
  inline constexpr bool is_monoid_v = ::tools::is_monoid<M>::value;
}


#line 6 "tools/square.hpp"

namespace tools {

  template <typename M>
  ::std::enable_if_t<::tools::is_monoid_v<M>, typename M::T> square(const typename M::T& x) {
    return M::op(x, x);
  }

  template <typename T>
  ::std::enable_if_t<!::tools::is_monoid_v<T>, T> square(const T& x) {
    return x * x;
  }
}


#line 9 "tools/pow.hpp"

namespace tools {

  template <typename M, typename E>
  ::std::enable_if_t<::std::is_integral_v<E>, typename M::T> pow(const typename M::T& base, const E exponent) {
    assert(exponent >= 0);
    return exponent == 0
      ? M::e()
      : exponent % 2 == 0
        ? ::tools::square<M>(::tools::pow<M>(base, exponent / 2))
        : M::op(::tools::pow<M>(base, exponent - 1), base);
  }

  template <typename T, typename E>
  ::std::enable_if_t<::std::is_integral_v<E>, T> pow(const T& base, const E exponent) {
    assert(exponent >= 0);
    return ::tools::pow<::tools::monoid::multiplies<T>>(base, exponent);
  }

  template <typename T, typename E>
  auto pow(const T base, const E exponent) -> ::std::enable_if_t<!::std::is_integral_v<E>, decltype(::std::pow(base, exponent))> {
    return ::std::pow(base, exponent);
  }
}

Back to top page