CGAL 4.12 - Algebraic Foundations
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. 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
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.