Concept for commutative ring (tools/commutative_ring.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2025-12-07 12:31:51+09:00
• Include: #include "tools/commutative_ring.hpp"

template <typename R>
concept commutative_ring = tools::ring<R> && tools::commutative_monoid<typename R::mul>;

It is a concept that represents a commutative ring. Note that semantic constraints must be guaranteed by the user.

Semantically, you can define that the results of R::add::op, R::add::inv and R::mul::op are undefined depending on the arguments. For example, you can define that integer addition is not defined for overflowing pairs.

Constraints

• When a user declares that a type <R> satisfies the concept of tools::commutative_ring, the following conditions must also be satisfied.
  • Semantic constraints of tools::ring<R> hold.
  • Semantic constraints of tools::commutative_monoid<typename R::mul> hold.

Time Complexity

• Not applicable

License

• CC0

Author

• anqooqie

Depends on

• Concept for commutative group (tools/commutative_group.hpp)
• Concept for commutative monoid (tools/commutative_monoid.hpp)
• Concept for group (tools/group.hpp)
• Concept for monoid (tools/monoid.hpp)
• Concept for ring (tools/ring.hpp)
• Concept for semiring (tools/semiring.hpp)

Required by

• Berlekamp-Massey algorithm (tools/berlekamp_massey.hpp)
• Bostan-Mori algorithm (tools/bostan_mori.hpp)
• Concept for field (tools/field.hpp)
• Matrix (tools/matrix.hpp)
• tools/matrix_mod2.hpp
• Polynomial (tools/polynomial.hpp)
• Polynomial interpolation (tools/polynomial_interpolation.hpp)
• Product of polynomials (tools/polynomial_product.hpp)
• Signed Stirling numbers of the first kind (tools/stirling_1st.hpp)

Verified with

• tests/berlekamp_massey.test.cpp
• tests/bostan_mori.test.cpp
• tests/matrix/determinant.test.cpp
• tests/matrix/inv.test.cpp
• tests/matrix/multiplies.test.cpp
• tests/matrix/rank.test.cpp
• tests/matrix/ring.test.cpp
• tests/matrix/solve.test.cpp
• tests/matrix/static.test.cpp
• tests/matrix_mod2/determinant.test.cpp
• tests/matrix_mod2/inv.test.cpp
• tests/matrix_mod2/multiplies.test.cpp
• tests/matrix_mod2/rank.test.cpp
• tests/matrix_mod2/solve.test.cpp
• tests/online_cumsum.test.cpp
• tests/pdsu.test.cpp
• tests/polynomial/extgcd.test.cpp
• tests/polynomial/multidimensional.test.cpp
• tests/polynomial/multipoint_evaluation.test.cpp
• tests/polynomial/multipoint_evaluation_other_mods.test.cpp
• tests/polynomial/naive_division.test.cpp
• tests/polynomial/ntt_division.test.cpp
• tests/polynomial/taylor_shift.test.cpp
• tests/polynomial_interpolation.test.cpp
• tests/polynomial_product.test.cpp
• tests/stirling_1st/consistent.test.cpp
• tests/stirling_1st/fixed_k.test.cpp
• tests/stirling_1st/fixed_n.test.cpp

Code

#ifndef TOOLS_COMMUTATIVE_RING_HPP
#define TOOLS_COMMUTATIVE_RING_HPP

#include "tools/commutative_monoid.hpp"
#include "tools/ring.hpp"

namespace tools {
  template <typename R>
  concept commutative_ring = tools::ring<R> && tools::commutative_monoid<typename R::mul>;
}

#endif

#line 1 "tools/commutative_ring.hpp"



#line 1 "tools/commutative_monoid.hpp"



#line 1 "tools/monoid.hpp"



#include <concepts>

namespace tools {
  template <typename M>
  concept monoid = requires(typename M::T x, typename M::T y) {
    { M::op(x, y) } -> std::same_as<typename M::T>;
    { M::e() } -> std::same_as<typename M::T>;
  };
}


#line 5 "tools/commutative_monoid.hpp"

namespace tools {
  template <typename M>
  concept commutative_monoid = tools::monoid<M>;
}


#line 1 "tools/ring.hpp"



#line 1 "tools/commutative_group.hpp"



#line 1 "tools/group.hpp"



#line 6 "tools/group.hpp"

namespace tools {
  template <typename G>
  concept group = tools::monoid<G> && requires(typename G::T x) {
    { G::inv(x) } -> std::same_as<typename G::T>;
  };
}


#line 6 "tools/commutative_group.hpp"

namespace tools {
  template <typename G>
  concept commutative_group = tools::group<G> && tools::commutative_monoid<G>;
}


#line 1 "tools/semiring.hpp"



#line 6 "tools/semiring.hpp"

namespace tools {
  template <typename R>
  concept semiring = tools::commutative_monoid<typename R::add> && tools::monoid<typename R::mul> && std::same_as<typename R::add::T, typename R::mul::T>;
}


#line 6 "tools/ring.hpp"

namespace tools {
  template <typename R>
  concept ring = tools::semiring<R> && tools::commutative_group<typename R::add>;
}


#line 6 "tools/commutative_ring.hpp"

namespace tools {
  template <typename R>
  concept commutative_ring = tools::ring<R> && tools::commutative_monoid<typename R::mul>;
}

Back to top page