CGAL 4.7 - Algebraic Foundations: AlgebraicStructureTraits_::DivMod Concept Reference

\( \newcommand{\E}{\mathrm{E}} \) \( \newcommand{\A}{\mathrm{A}} \) \( \newcommand{\R}{\mathrm{R}} \) \( \newcommand{\N}{\mathrm{N}} \) \( \newcommand{\Q}{\mathrm{Q}} \) \( \newcommand{\Z}{\mathrm{Z}} \) \( \def\ccSum #1#2#3{ \sum_{#1}^{#2}{#3} } \def\ccProd #1#2#3{ \sum_{#1}^{#2}{#3} }\)

CGAL 4.7 - Algebraic Foundations

All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Groups Pages
List of all members
AlgebraicStructureTraits_::DivMod Concept Reference
Concepts

## Definition

`AdaptableFunctor` computes both integral quotient and remainder of division with remainder. The quotient \( q\) and remainder \( r\) are computed such that \( x = q*y + r\) and \( |r| < |y|\) with respect to the proper integer norm of the represented ring. For integers this norm is the absolute value. For univariate polynomials this norm is the degree. In particular, \( r\) is chosen to be \( 0\) if possible. Moreover, we require \( q\) to be minimized with respect to the proper integer norm.

Note that the last condition is needed to ensure a unique computation of the pair \( (q,r)\). However, an other option is to require minimality for \( |r|\), with the advantage that a mod(x,y) operation would return the unique representative of the residue class of \( x\) with respect to \( y\), e.g. \( mod(2,3)\) should return \( -1\). But this conflicts with nearly all current implementation of integer types. From there, we decided to stay conform with common implementations and require \( q\) to be computed as \( x/y\) rounded towards zero.

The following table illustrates the behavior for integers:

x | y | q | r

3 | 3 | 1 | 0
2 | 3 | 0 | 2
1 | 3 | 0 | 1
0 | 3 | 0 | 0
-1 | 3 | 0 | -1
-2 | 3 | 0 | -2
-3 | 3 | -1 | 0

x | y | q | r

3 | -3 | -1 | 0
2 | -3 | 0 | 2
1 | -3 | 0 | 1
0 | -3 | 0 | 0
-1 | -3 | 0 | -1
-2 | -3 | 0 | -2
-3 | -3 | 1 | 0

Refines:
  `AdaptableFunctor`

See Also
  `AlgebraicStructureTraits`
  `AlgebraicStructureTraits_::Mod`
  `AlgebraicStructureTraits_::Div`

## Types

typedef unspecified_type | result_type
| Is void.
typedef unspecified_type | first_argument_type
| Is `AlgebraicStructureTraits::Type`.
typedef unspecified_type | second_argument_type
| Is `AlgebraicStructureTraits::Type`.
typedef unspecified_type | third_argument_type
| Is `AlgebraicStructureTraits::Type&`.
typedef unspecified_type | fourth_argument_type
| Is `AlgebraicStructureTraits::Type&`.

## Operations

result_type | operator() (first_argument_type x, second_argument_type y, third_argument_type q, fourth_argument_type r)
| computes the quotient \( q\) and remainder \( r\), such that \( x = q*y + r\) and \( r\) minimal with respect to the Euclidean Norm on `Type`.
template<class NT1 , class NT2 >
result_type | operator() (NT1 x, NT2 y, third_argument_type q, fourth_argument_type r)
| This operator is defined if `NT1` and `NT2` are `ExplicitInteroperable` with coercion type `AlgebraicStructureTraits::Type`.