Algebraic Foundations Reference

Michael Hemmer

This package defines what algebra means for CGAL, in terms of concepts, classes and functions. The main features are: (i) explicit concepts for interoperability of types (ii) separation between algebraic types (not necessarily embeddable into the reals), and number types (embeddable into the reals).

Introduced in: CGAL 3.3
BibTeX: cgal:h-af-20b
License: LGPL

Classified Reference Pages

Algebraic Structures

Concepts

• IntegralDomainWithoutDivision
• IntegralDomain
• UniqueFactorizationDomain
• EuclideanRing
• Field
• FieldWithSqrt
• FieldWithKthRoot
• FieldWithRootOf
• AlgebraicStructureTraits
• AlgebraicStructureTraits_::IsZero
• AlgebraicStructureTraits_::IsOne
• AlgebraicStructureTraits_::Square
• AlgebraicStructureTraits_::Simplify
• AlgebraicStructureTraits_::UnitPart
• AlgebraicStructureTraits_::IntegralDivision
• AlgebraicStructureTraits_::Divides
• AlgebraicStructureTraits_::Gcd
• AlgebraicStructureTraits_::DivMod
• AlgebraicStructureTraits_::Div
• AlgebraicStructureTraits_::Mod
• AlgebraicStructureTraits_::Inverse
• AlgebraicStructureTraits_::Sqrt
• AlgebraicStructureTraits_::IsSquare
• AlgebraicStructureTraits_::KthRoot
• AlgebraicStructureTraits_::RootOf

Classes

• CGAL::Algebraic_structure_traits<T>
• CGAL::Integral_domain_without_division_tag
• CGAL::Integral_domain_tag
• CGAL::Field_tag
• CGAL::Field_with_sqrt_tag
• CGAL::Unique_factorization_domain_tag
• CGAL::Euclidean_ring_tag

Global Functions

• CGAL::is_zero()
• CGAL::is_one()
• CGAL::square()
• CGAL::simplify()
• CGAL::unit_part()
• CGAL::integral_division()
• CGAL::is_square()
• CGAL::gcd()
• CGAL::div_mod()
• CGAL::div()
• CGAL::mod()
• CGAL::inverse()
• CGAL::sqrt()
• CGAL::kth_root()
• CGAL::root_of()

Real Embeddable

Concepts

• RealEmbeddable
• RealEmbeddableTraits
• RealEmbeddableTraits_::IsZero
• RealEmbeddableTraits_::Abs
• RealEmbeddableTraits_::Sgn
• RealEmbeddableTraits_::IsPositive
• RealEmbeddableTraits_::IsNegative
• RealEmbeddableTraits_::Compare
• RealEmbeddableTraits_::ToDouble
• RealEmbeddableTraits_::ToInterval

Classes

• CGAL::Real_embeddable_traits<T>

Global Functions

• CGAL::is_zero()
• CGAL::abs()
• CGAL::sign()
• CGAL::is_positive()
• CGAL::is_negative()
• CGAL::compare()
• CGAL::to_double()
• CGAL::to_interval()

Real Number Types

Concepts

• RingNumberType
• FieldNumberType

Interoperability

Concepts

• ExplicitInteroperable
• ImplicitInteroperable

Classes

• CGAL::Coercion_traits<A,B>

Fractions

Concepts

• Fraction
• FractionTraits
• FractionTraits_::Decompose
• FractionTraits_::Compose
• FractionTraits_::CommonFactor

Classes

• CGAL::Fraction_traits<T>

Miscellaneous

Concepts

• FromIntConstructible
• FromDoubleConstructible

Modules
	Concepts

Classes
class	CGAL::Algebraic_structure_traits< T >
	An instance of Algebraic_structure_traits is a model of AlgebraicStructureTraits, where T is the associated type. More...
struct	CGAL::Euclidean_ring_tag
	Tag indicating that a type is a model of the EuclideanRing concept. More...
struct	CGAL::Field_tag
	Tag indicating that a type is a model of the Field concept. More...
struct	CGAL::Field_with_kth_root_tag
	Tag indicating that a type is a model of the FieldWithKthRoot concept. More...
struct	CGAL::Field_with_root_of_tag
	Tag indicating that a type is a model of the FieldWithRootOf concept. More...
struct	CGAL::Field_with_sqrt_tag
	Tag indicating that a type is a model of the FieldWithSqrt concept. More...
struct	CGAL::Integral_domain_tag
	Tag indicating that a type is a model of the IntegralDomain concept. More...
struct	CGAL::Integral_domain_without_division_tag
	Tag indicating that a type is a model of the IntegralDomainWithoutDivision concept. More...
struct	CGAL::Unique_factorization_domain_tag
	Tag indicating that a type is a model of the UniqueFactorizationDomain concept. More...
struct	CGAL::Coercion_traits< A, B >
	An instance of Coercion_traits reflects the type coercion of the types A and B, it is symmetric in the two template arguments. More...
class	CGAL::Fraction_traits< T >
	An instance of Fraction_traits is a model of FractionTraits, where T is the associated type. More...
class	CGAL::Real_embeddable_traits< T >
	An instance of Real_embeddable_traits is a model of RealEmbeddableTraits, where T is the associated type. More...

Functions
template<class NT >
NT	CGAL::abs (const NT &x)
	The template function abs() returns the absolute value of a number. More...
template<class NT1 , class NT2 >
result_type	CGAL::compare (const NT &x, const NT &y)
	The template function compare() compares the first argument with respect to the second, i.e. it returns CGAL::LARGER if \( x\) is larger then \( y\). More...
template<class NT1 , class NT2 >
result_type	CGAL::div (const NT1 &x, const NT2 &y)
	The function div() computes the integral quotient of division with remainder. More...
template<class NT1 , class NT2 >
void	CGAL::div_mod (const NT1 &x, const NT2 &y, result_type &q, result_type &r)
	computes the quotient \( q\) and remainder \( r\), such that \( x = q*y + r\) and \( r\) minimal with respect to the Euclidean Norm of the result_type. More...
template<class NT1 , class NT2 >
result_type	CGAL::gcd (const NT1 &x, const NT2 &y)
	The function gcd() computes the greatest common divisor of two values. More...
template<class NT1 , class NT2 >
result_type	CGAL::integral_division (const NT1 &x, const NT2 &y)
	The function integral_division() (a.k.a. exact division or division without remainder) maps ring elements \( (x,y)\) to ring element \( z\) such that \( x = yz\) if such a \( z\) exists (i.e. if \( x\) is divisible by \( y\)). More...
template<class NT >
NT	CGAL::inverse (const NT &x)
	The function inverse() returns the inverse element with respect to multiplication. More...
result_type	CGAL::is_negative (const NT &x)
	The template function is_negative() determines if a value is negative or not. More...
template<class NT >
result_type	CGAL::is_one (const NT &x)
	The function is_one() determines if a value is equal to 1 or not. More...
result_type	CGAL::is_positive (const NT &x)
	The template function is_positive() determines if a value is positive or not. More...
template<class NT >
result_type	CGAL::is_square (const NT &x)
	An ring element \( x\) is said to be a square iff there exists a ring element \( y\) such that \( x= y*y\). More...
template<class NT >
result_type	CGAL::is_square (const NT &x, NT &y)
	An ring element \( x\) is said to be a square iff there exists a ring element \( y\) such that \( x= y*y\). More...
template<class NT >
result_type	CGAL::is_zero (const NT &x)
	The function is_zero() determines if a value is equal to 0 or not. More...
template<class NT >
NT	CGAL::kth_root (int k, const NT &x)
	The function kth_root() returns the k-th root of a value. More...
template<class NT1 , class NT2 >
result_type	CGAL::mod (const NT1 &x, const NT2 &y)
	The function mod() computes the remainder of division with remainder. More...
template<class InputIterator >
NT	CGAL::root_of (int k, InputIterator begin, InputIterator end)
	returns the k-th real root of the univariate polynomial, which is defined by the iterator range, where begin refers to the constant term. More...
template<class NT >
result_type	CGAL::sign (const NT &x)
	The template function sign() returns the sign of its argument. More...
template<class NT >
void	CGAL::simplify (const NT &x)
	The function simplify() may simplify a given object. More...
template<class NT >
NT	CGAL::sqrt (const NT &x)
	The function sqrt() returns the square root of a value. More...
template<class NT >
NT	CGAL::square (const NT &x)
	The function square() returns the square of a number. More...
template<class NT >
double	CGAL::to_double (const NT &x)
	The template function to_double() returns a double approximation of a number. More...
template<class NT >
std::pair< double, double >	CGAL::to_interval (const NT &x)
	The template function to_interval() computes for a given real embeddable number \( x\) a double interval containing \( x\). More...
template<class NT >
NT	CGAL::unit_part (const NT &x)
	The function unit_part() computes the unit part of a given ring element. More...

Function Documentation

abs()

template<class NT >

NT CGAL::abs

(

const NT &

x

)

#include <CGAL/number_utils.h>

The template function abs() returns the absolute value of a number.

The function is defined if the argument type is a model of the RealEmbeddable concept.

See also

RealEmbeddable

RealEmbeddableTraits_::Abs

compare()

template<class NT1 , class NT2 >

result_type CGAL::compare	(	const NT &	x,
		const NT &	y
	)

#include <CGAL/number_utils.h>

The template function compare() compares the first argument with respect to the second, i.e. it returns CGAL::LARGER if \( x\) is larger then \( y\).

In case the argument types NT1 and NT2 differ, compare is performed with the semantic of the type determined via Coercion_traits. The function is defined if this type is a model of the RealEmbeddable concept.

The result_type is convertible to CGAL::Comparison_result.

See also

RealEmbeddable

RealEmbeddableTraits_::Compare

div()

template<class NT1 , class NT2 >

result_type CGAL::div	(	const NT1 &	x,
		const NT2 &	y
	)

#include <CGAL/number_utils.h>

The function div() computes the integral quotient of division with remainder.

In case the argument types NT1 and NT2 differ, the result_type is determined via Coercion_traits.

Thus, the result_type is well defined if NT1 and NT2 are a model of ExplicitInteroperable.

The actual div is performed with the semantic of that type.

The function is defined if result_type is a model of the EuclideanRing concept.

See also

EuclideanRing

AlgebraicStructureTraits_::Div

CGAL::mod()

CGAL::div_mod()

div_mod()

template<class NT1 , class NT2 >

void CGAL::div_mod	(	const NT1 &	x,
		const NT2 &	y,
		result_type &	q,
		result_type &	r
	)

#include <CGAL/number_utils.h>

computes the quotient \( q\) and remainder \( r\), such that \( x = q*y + r\) and \( r\) minimal with respect to the Euclidean Norm of the result_type.

The function div_mod() computes the integral quotient and remainder of division with remainder.

In case the argument types NT1 and NT2 differ, the result_type is determined via Coercion_traits.

Thus, the result_type is well defined if NT1 and NT2 are a model of ExplicitInteroperable.

The actual div_mod is performed with the semantic of that type.

The function is defined if result_type is a model of the EuclideanRing concept.

See also

EuclideanRing

AlgebraicStructureTraits_::DivMod

CGAL::mod()

CGAL::div()

gcd()

template<class NT1 , class NT2 >

result_type CGAL::gcd	(	const NT1 &	x,
		const NT2 &	y
	)

#include <CGAL/number_utils.h>

The function gcd() computes the greatest common divisor of two values.

In case the argument types NT1 and NT2 differ, the result_type is determined via Coercion_traits.

Thus, the result_type is well defined if NT1 and NT2 are a model of ExplicitInteroperable.

The actual gcd is performed with the semantic of that type.

The function is defined if result_type is a model of the UniqueFactorizationDomain concept.

See also

UniqueFactorizationDomain

AlgebraicStructureTraits_::Gcd

Examples:

Algebraic_foundations/integralize.cpp.

integral_division()

template<class NT1 , class NT2 >

result_type CGAL::integral_division	(	const NT1 &	x,
		const NT2 &	y
	)

#include <CGAL/number_utils.h>

The function integral_division() (a.k.a. exact division or division without remainder) maps ring elements \( (x,y)\) to ring element \( z\) such that \( x = yz\) if such a \( z\) exists (i.e. if \( x\) is divisible by \( y\)).

Otherwise the effect of invoking this operation is undefined. Since the ring represented is an integral domain, \( z\) is uniquely defined if it exists.

In case the argument types NT1 and NT2 differ, the result_type is determined via Coercion_traits.

Thus, the result_type is well defined if NT1 and NT2 are a model of ExplicitInteroperable.

The actual integral_division is performed with the semantic of that type.

The function is defined if result_type is a model of the IntegralDomain concept.

See also

IntegralDomain

AlgebraicStructureTraits_::IntegralDivision

Examples:

Algebraic_foundations/integralize.cpp.

inverse()

template<class NT >

NT CGAL::inverse

(

const NT &

x

)

#include <CGAL/number_utils.h>

The function inverse() returns the inverse element with respect to multiplication.

The function is defined if the argument type is a model of the Field concept.

Precondition

\( x \neq0\).

See also

Field

AlgebraicStructureTraits_::Inverse

is_negative()

result_type CGAL::is_negative

(

const NT &

x

)

#include <CGAL/number_utils.h>

The template function is_negative() determines if a value is negative or not.

The function is defined if the argument type is a model of the RealEmbeddable concept.

The result_type is convertible to bool.

See also

RealEmbeddable

RealEmbeddableTraits_::IsNegative

is_one()

template<class NT >

result_type CGAL::is_one

(

const NT &

x

)

#include <CGAL/number_utils.h>

The function is_one() determines if a value is equal to 1 or not.

The function is defined if the argument type is a model of the IntegralDomainWithoutDivision concept.

The result_type is convertible to bool.

See also

IntegralDomainWithoutDivision

AlgebraicStructureTraits_::IsOne

is_positive()

result_type CGAL::is_positive

(

const NT &

x

)

#include <CGAL/number_utils.h>

The template function is_positive() determines if a value is positive or not.

The function is defined if the argument type is a model of the RealEmbeddable concept.

The result_type is convertible to bool.

See also

RealEmbeddable

RealEmbeddableTraits_::IsPositive

is_square() [1/2]

template<class NT >

result_type CGAL::is_square

(

const NT &

x

)

#include <CGAL/number_utils.h>

An ring element \( x\) is said to be a square iff there exists a ring element \( y\) such that \( x= y*y\).

In case the ring is a UniqueFactorizationDomain, \( y\) is uniquely defined up to multiplication by units.

The function is_square() is available if Algebraic_structure_traits::Is_square is not the CGAL::Null_functor.

The result_type is convertible to bool.

See also

UniqueFactorizationDomain

AlgebraicStructureTraits_::IsSquare

is_square() [2/2]

template<class NT >

result_type CGAL::is_square	(	const NT &	x,
		NT &	y
	)

#include <CGAL/number_utils.h>

An ring element \( x\) is said to be a square iff there exists a ring element \( y\) such that \( x= y*y\).

In case the ring is a UniqueFactorizationDomain, \( y\) is uniquely defined up to multiplication by units.

The function is_square() is available if Algebraic_structure_traits::Is_square is not the CGAL::Null_functor.

The result_type is convertible to bool.

See also

UniqueFactorizationDomain

AlgebraicStructureTraits_::IsSquare

is_zero()

template<class NT >

result_type CGAL::is_zero

(

const NT &

x

)

#include <CGAL/number_utils.h>

The function is_zero() determines if a value is equal to 0 or not.

The function is defined if the argument type is a model of the RealEmbeddable or of the IntegralDomainWithoutDivision concept.

The result_type is convertible to bool.

See also

RealEmbeddable

RealEmbeddableTraits_::IsZero

IntegralDomainWithoutDivision

AlgebraicStructureTraits_::IsZero

kth_root()

template<class NT >

NT CGAL::kth_root	(	int	k,
		const NT &	x
	)

#include <CGAL/number_utils.h>

The function kth_root() returns the k-th root of a value.

The function is defined if the second argument type is a model of the FieldWithKthRoot concept.

See also

FieldWithKthRoot

AlgebraicStructureTraits_::KthRoot

mod()

template<class NT1 , class NT2 >

result_type CGAL::mod	(	const NT1 &	x,
		const NT2 &	y
	)

#include <CGAL/number_utils.h>

The function mod() computes the remainder of division with remainder.

In case the argument types NT1 and NT2 differ, the result_type is determined via Coercion_traits.

Thus, the result_type is well defined if NT1 and NT2 are a model of ExplicitInteroperable.

The actual mod is performed with the semantic of that type.

The function is defined if result_type is a model of the EuclideanRing concept.

See also

EuclideanRing

AlgebraicStructureTraits_::DivMod

CGAL::div_mod()

CGAL::div()

root_of()

template<class InputIterator >

NT CGAL::root_of	(	int	k,
		InputIterator	begin,
		InputIterator	end
	)

#include <CGAL/number_utils.h>

returns the k-th real root of the univariate polynomial, which is defined by the iterator range, where begin refers to the constant term.

The function root_of() computes a real root of a square-free univariate polynomial.

The function is defined if the value type, NT, of the iterator range is a model of the FieldWithRootOf concept.

Precondition

The polynomial is square-free.

See also

FieldWithRootOf

AlgebraicStructureTraits_::RootOf

sign()

template<class NT >

result_type CGAL::sign

(

const NT &

x

)

#include <CGAL/number_utils.h>

The template function sign() returns the sign of its argument.

The function is defined if the argument type is a model of the RealEmbeddable concept.

The result_type is convertible to CGAL::Sign.

See also

RealEmbeddable

RealEmbeddableTraits_::Sgn

Examples:

Algebraic_foundations/algebraic_structure_dispatch.cpp.

simplify()

template<class NT >

void CGAL::simplify

(

const NT &

x

)

#include <CGAL/number_utils.h>

The function simplify() may simplify a given object.

The function is defined if the argument type is a model of the IntegralDomainWithoutDivision concept.

See also

IntegralDomainWithoutDivision

AlgebraicStructureTraits_::Simplify

sqrt()

template<class NT >

NT CGAL::sqrt

(

const NT &

x

)

#include <CGAL/number_utils.h>

The function sqrt() returns the square root of a value.

The function is defined if the argument type is a model of the FieldWithSqrt concept.

See also

FieldWithSqrt

AlgebraicStructureTraits_::Sqrt

square()

template<class NT >

NT CGAL::square

(

const NT &

x

)

#include <CGAL/number_utils.h>

The function square() returns the square of a number.

The function is defined if the argument type is a model of the IntegralDomainWithoutDivision concept.

See also

IntegralDomainWithoutDivision

AlgebraicStructureTraits_::Square

to_double()

template<class NT >

double CGAL::to_double

(

const NT &

x

)

#include <CGAL/number_utils.h>

The template function to_double() returns a double approximation of a number.

Note that in general, the value returned is not guaranteed to be the same when called several times on the same number. For example, if NT is a lazy number type (such as an instance of CGAL::Lazy_exact_nt), the double approximation returned might be affected by an exact computation internally triggered (that might have improved the double approximation).

The function is defined if the argument type is a model of the RealEmbeddable concept.

Remark: In order to control the quality of approximation one has to resort to methods that are specific to NT. There are no general guarantees whatsoever.

See also

RealEmbeddable

RealEmbeddableTraits_::ToDouble

to_interval()

template<class NT >

std::pair<double,double> CGAL::to_interval

(

const NT &

x

)

#include <CGAL/number_utils.h>

The template function to_interval() computes for a given real embeddable number \( x\) a double interval containing \( x\).

This interval is represented by a std::pair<double,double>. The function is defined if the argument type is a model of the RealEmbeddable concept.

See also

RealEmbeddable

RealEmbeddableTraits_::ToInterval

unit_part()

template<class NT >

NT CGAL::unit_part

(

const NT &

x

)

#include <CGAL/number_utils.h>

The function unit_part() computes the unit part of a given ring element.

The function is defined if the argument type is a model of the IntegralDomainWithoutDivision concept.

See also

IntegralDomainWithoutDivision

AlgebraicStructureTraits_::UnitPart

Examples:

Algebraic_foundations/algebraic_structure_dispatch.cpp.