AlgebraicStructureTraits::DivMod

Navigation: Up, Table of Contents, Package Overview, Bibliography, Index, Title Page , Acknowledging CGAL

AlgebraicStructureTraits::DivMod

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. ¹ 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 truth 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

Types

AlgebraicStructureTraits::DivMod::result_type
	Is AlgebraicStructureTraits::Type.
AlgebraicStructureTraits::DivMod::first_argument_type
	Is AlgebraicStructureTraits::Type.
AlgebraicStructureTraits::DivMod::second_argument_type
	Is AlgebraicStructureTraits::Type.
AlgebraicStructureTraits::DivMod::third_argument_type
	Is AlgebraicStructureTraits::Type&.
AlgebraicStructureTraits::DivMod::fourth_argument_type
	Is AlgebraicStructureTraits::Type&.

Operations

result_type

div_mod ( 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

div_mod ( NT1 x , NT2 y , third_argument_type q , fourth_argument_type r )

This operator is well defined if NT1 and NT2 are ExplicitInteroperable with coercion type AlgebraicStructureTraits::Type.

Footnotes


¹	For integers this norm is the absolute value. For univariate polynomials this norm is the degree.

Next: AlgebraicStructureTraits::Div

Navigation: Up, Table of Contents, Package Overview, Bibliography, Index, Title Page , Acknowledging CGAL

CGAL Open Source Project. Release 3.3.1. 25 August 2007.