Euclidean Ring

Description

The EuclideanRing concept represents a commutative Ring that can also be endowed with a division algorithm.

A Ring defines a binary operation often called multiplication that can be used to combine two elements of the ring into a new element of the ring. An Euclidean ring, also called an Euclidean domain, adds the ability to define a special function that generalizes the Euclidean division of integers.

However, an Euclidean ring must also satisfy one more property, which is that of having no non-zero zero divisors. In a Ring (R, +, *), it follows quite easily from the axioms that x * 0 == 0 for any ring element x. However, there is nothing that mandates 0 to be the only ring element sending other elements to 0. Hence, in some Rings, it is possible to have elements x and y such that x * y == 0 while not having x == 0 nor y == 0. We call these elements divisors of zero, or zero divisors. For example, this situation arises in the Ring of integers modulo 4 (the set {0, 1, 2, 3}) with addition and multiplication mod 4 as binary operations. In this case, we have that

2 * 2 == 4
      == 0 (mod 4)

even though 2 != 0 (mod 4).

Following this line of thought, an Euclidean ring requires its only zero divisor is zero itself. In other words, the multiplication in an Euclidean won't send two non-zero elements to zero. Also note that since multiplication in a Ring is not necessarily commutative, it is not always the case that

x * y == 0  implies  y * x == 0

To be rigorous, we should then distinguish between elements that are zero divisors when multiplied to the right and to the left. Fortunately, the concept of an Euclidean ring requires the Ring multiplication to be commutative. Hence,

x * y == y * x

and we do not have to distinguish between left and right zero divisors.

Typical examples of Euclidean rings include integers and polynomials over a field. The method names used here refer to the Euclidean ring of integers under the usual addition, multiplication and division operations.

Minimal complete definition

div and mod satisfying the laws below

Laws

To simplify the reading, we will use the +, *, / and % operators with infix notation to denote the application of the corresponding methods in Monoid, Group, Ring and EuclideanRing. For all objects a and b of an EuclideanRing R, the following laws must be satisfied:

a * b == b * a // commutativity
(a / b) * b + a % b == a    if b is non-zero
zero<R>() % b == zero<R>()  if b is non-zero

Refined concepts

Monoid, Group, Ring

Concrete models

hana::integral_constant

Free model for non-boolean integral data types

A data type T is integral if std::is_integral<T>::value is true. For a non-boolean integral data type T, a model of EuclideanRing is automatically defined by using the Ring model provided for arithmetic data types and setting

div(x, y) = (x / y)
mod(x, y)  = (x % y)

Note

The rationale for not providing an EuclideanRing model for bool is the same as for not providing Monoid, Group and Ring models.

Variables
constexpr auto	boost::hana::div
	Generalized integer division. More...
constexpr auto	boost::hana::mod
	Generalized integer modulus. More...

Variable Documentation

div

constexpr auto boost::hana::div

constexpr

#include <boost/hana/fwd/div.hpp>

Initial value:

= [](auto&& x, auto&& y) -> decltype(auto) {
        return tag-dispatched;
    }

Generalized integer division.

Cross-type version of the method

The div method is "overloaded" to handle distinct data types with certain properties. Specifically, div is defined for distinct data types A and B such that

1. A and B share a common data type C, as determined by the common metafunction
2. A, B and C are all EuclideanRings when taken individually
3. to<C> : A -> B and to<C> : B -> C are Ring-embeddings, as determined by the is_embedding metafunction.

In that case, the div method is defined as

div(x, y) = div(to<C>(x), to<C>(y))

Example

// Copyright Louis Dionne 2013-2017
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE.md or copy at http://boost.org/LICENSE_1_0.txt)
 
#include <boost/hana/assert.hpp>
#include <boost/hana/div.hpp>
#include <boost/hana/equal.hpp>
#include <boost/hana/integral_constant.hpp>
namespace hana = boost::hana;
 
 
BOOST_HANA_CONSTANT_CHECK(hana::div(hana::int_c<6>, hana::int_c<3>) == hana::int_c<2>);
BOOST_HANA_CONSTANT_CHECK(hana::div(hana::int_c<6>, hana::int_c<4>) == hana::int_c<1>);
 
static_assert(hana::div(6, 3) == 2, "");
static_assert(hana::div(6, 4) == 1, "");
 
int main() { }

mod

constexpr auto boost::hana::mod

constexpr

#include <boost/hana/fwd/mod.hpp>

Initial value:

= [](auto&& x, auto&& y) -> decltype(auto) {
        return tag-dispatched;
    }

Generalized integer modulus.

Given two elements of an EuclideanRing x and y, with y nonzero, mod returns the modulus of the division of x by y. In other words, mod can be seen as an equivalent to %.

Cross-type version of the method

The mod method is "overloaded" to handle distinct data types with certain properties. Specifically, mod is defined for distinct data types A and B such that

1. A and B share a common data type C, as determined by the common metafunction
2. A, B and C are all EuclideanRings when taken individually
3. to<C> : A -> B and to<C> : B -> C are Ring-embeddings, as determined by the is_embedding metafunction.

In that case, mod is defined as

mod(x, y) = mod(to<C>(x), to<C>(y))

Example

// Copyright Louis Dionne 2013-2017
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE.md or copy at http://boost.org/LICENSE_1_0.txt)
 
#include <boost/hana/assert.hpp>
#include <boost/hana/equal.hpp>
#include <boost/hana/integral_constant.hpp>
#include <boost/hana/mod.hpp>
namespace hana = boost::hana;
 
 
BOOST_HANA_CONSTANT_CHECK(hana::mod(hana::int_c<6>, hana::int_c<4>) == hana::int_c<2>);
BOOST_HANA_CONSTANT_CHECK(hana::mod(hana::int_c<-6>, hana::int_c<4>) == hana::int_c<-2>);
static_assert(hana::mod(6, 4) == 2, "");
 
int main() { }