CGAL 4.8.2 - Algebraic Foundations
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-16b

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

class  CGAL::Euclidean_ring_tag
Tag indicating that a type is a model of the EuclideanRing concept. More...

class  CGAL::Field_tag
Tag indicating that a type is a model of the Field concept. More...

class  CGAL::Field_with_kth_root_tag
Tag indicating that a type is a model of the FieldWithKthRoot concept. More...

class  CGAL::Field_with_root_of_tag
Tag indicating that a type is a model of the FieldWithRootOf concept. More...

class  CGAL::Field_with_sqrt_tag
Tag indicating that a type is a model of the FieldWithSqrt concept. More...

class  CGAL::Integral_domain_tag
Tag indicating that a type is a model of the IntegralDomain concept. More...

class  CGAL::Integral_domain_without_division_tag
Tag indicating that a type is a model of the IntegralDomainWithoutDivision concept. More...

class  CGAL::Unique_factorization_domain_tag
Tag indicating that a type is a model of the UniqueFactorizationDomain concept. More...

class  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 an 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

template<class NT >
 NT CGAL::abs ( const NT & x)

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.

RealEmbeddable
RealEmbeddableTraits_::Abs

#include <CGAL/number_utils.h>

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$$.

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.

RealEmbeddable
RealEmbeddableTraits_::Compare

#include <CGAL/number_utils.h>

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.

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.

EuclideanRing
AlgebraicStructureTraits_::Div
CGAL::mod()
CGAL::div_mod()

#include <CGAL/number_utils.h>

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.

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.

EuclideanRing
AlgebraicStructureTraits_::DivMod
CGAL::mod()
CGAL::div()

#include <CGAL/number_utils.h>

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.

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.

UniqueFactorizationDomain
AlgebraicStructureTraits_::Gcd

#include <CGAL/number_utils.h>

Examples:
Algebraic_foundations/integralize.cpp.
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$$).

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.

IntegralDomain
AlgebraicStructureTraits_::IntegralDivision

#include <CGAL/number_utils.h>

Examples:
Algebraic_foundations/integralize.cpp.
template<class NT >
 NT CGAL::inverse ( const NT & x)

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$$.
Field
AlgebraicStructureTraits_::Inverse

#include <CGAL/number_utils.h>

 result_type CGAL::is_negative ( const NT & x)

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.

RealEmbeddable
RealEmbeddableTraits_::IsNegative

#include <CGAL/number_utils.h>

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.

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

The result_type is convertible to bool.

IntegralDomainWithoutDivision
AlgebraicStructureTraits_::IsOne

#include <CGAL/number_utils.h>

 result_type CGAL::is_positive ( const NT & x)

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.

RealEmbeddable
RealEmbeddableTraits_::IsPositive

#include <CGAL/number_utils.h>

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$$.

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.

UniqueFactorizationDomain
AlgebraicStructureTraits_::IsSquare

#include <CGAL/number_utils.h>

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$$.

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.

UniqueFactorizationDomain
AlgebraicStructureTraits_::IsSquare

#include <CGAL/number_utils.h>

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.

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.

RealEmbeddable
RealEmbeddableTraits_::IsZero
IntegralDomainWithoutDivision
AlgebraicStructureTraits_::IsZero

#include <CGAL/number_utils.h>

template<class NT >
 NT CGAL::kth_root ( int k, const NT & x )

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.

FieldWithKthRoot
AlgebraicStructureTraits_::KthRoot

#include <CGAL/number_utils.h>

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.

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.

EuclideanRing
AlgebraicStructureTraits_::DivMod
CGAL::div_mod()
CGAL::div()

#include <CGAL/number_utils.h>

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.

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.
FieldWithRootOf
AlgebraicStructureTraits_::RootOf

#include <CGAL/number_utils.h>

template<class NT >
 result_type CGAL::sign ( const NT & x)

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.

RealEmbeddable
RealEmbeddableTraits_::Sgn

#include <CGAL/number_utils.h>

Examples:
Algebraic_foundations/algebraic_structure_dispatch.cpp.
template<class NT >
 void CGAL::simplify ( const NT & x)

The function simplify() may simplify a given object.

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

IntegralDomainWithoutDivision
AlgebraicStructureTraits_::Simplify

#include <CGAL/number_utils.h>

template<class NT >
 NT CGAL::sqrt ( const NT & x)

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.

FieldWithSqrt
AlgebraicStructureTraits_::Sqrt

#include <CGAL/number_utils.h>

template<class NT >
 NT CGAL::square ( const NT & x)

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

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

IntegralDomainWithoutDivision
AlgebraicStructureTraits_::Square

#include <CGAL/number_utils.h>

template<class NT >
 double CGAL::to_double ( const NT & x)

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

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.

RealEmbeddable
RealEmbeddableTraits_::ToDouble

#include <CGAL/number_utils.h>

template<class NT >
 std::pair CGAL::to_interval ( const NT & x)

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.

RealEmbeddable
RealEmbeddableTraits_::ToInterval

#include <CGAL/number_utils.h>

template<class NT >
 NT CGAL::unit_part ( const NT & x)

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.