Loading [MathJax]/extensions/TeX/newcommand.js
\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.12.1 - Algebraic Foundations
All Classes Namespaces Files Functions Variables Typedefs Enumerations Friends Modules Pages
AlgebraicStructureTraits_::DivMod Concept Reference

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. [1] 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.
 
  1. ^For integers this norm is the absolute value. For univariate polynomials this norm is the degree.