CGAL 5.3 - Algebraic Foundations
Algebraic Foundations Reference

Algebraic_foundations2.png
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-21a
License: LGPL

Classified Reference Pages

Algebraic Structures

Concepts

Classes

Global Functions

Real Embeddable

Concepts

Classes

Global Functions

Real Number Types

Concepts

Interoperability

Concepts

Classes

Fractions

Concepts

Classes

Miscellaneous

Concepts

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 than \( 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 than \( 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.