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-24b
License: LGPL

Classified Reference Pages

Algebraic Structures

Concepts

Classes

Global Functions

Real Embeddable

Concepts

Classes

CGAL::Real_embeddable_traits<T>

Global Functions

Real Number Types

Concepts

RingNumberType
FieldNumberType

Interoperability

Concepts

Classes

CGAL::Coercion_traits<A,B>

Fractions

Concepts

Classes

CGAL::Fraction_traits<T>

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.

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

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.

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

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.

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

template<class NT >
NT	CGAL::inverse (const NT &x)
	The function `inverse()` returns the inverse element with respect to multiplication.

result_type	CGAL::is_negative (const NT &x)
	The template function `is_negative()` determines if a value is negative or not.

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.

result_type	CGAL::is_positive (const NT &x)
	The template function `is_positive()` determines if a value is positive or not.

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

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

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.

template<class NT >
NT	CGAL::kth_root (int k, const NT &x)
	The function `kth_root()` returns the k-th root of a value.

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.

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.

template<class NT >
result_type	CGAL::sign (const NT &x)
	The template function `sign()` returns the sign of its argument.

template<class NT >
void	CGAL::simplify (const NT &x)
	The function `simplify()` may simplify a given object.

template<class NT >
NT	CGAL::sqrt (const NT &x)
	The function `sqrt()` returns the square root of a value.

template<class NT >
NT	CGAL::square (const NT &x)
	The function `square()` returns the square of a number.

template<class NT >
double	CGAL::to_double (const NT &x)
	The template function `to_double()` returns a double approximation of a number.

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

template<class NT >
NT	CGAL::unit_part (const NT &x)
	The function `unit_part()` computes the unit part of a given ring element.

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

◆ 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

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

Classes

Functions

Function Documentation

◆ abs()

◆ compare()

◆ div()

◆ div_mod()

◆ gcd()

◆ integral_division()

◆ inverse()

◆ is_negative()

◆ is_one()

◆ is_positive()

◆ is_square() [1/2]

◆ is_square() [2/2]

◆ is_zero()

◆ kth_root()

◆ mod()

◆ root_of()

◆ sign()

◆ simplify()

◆ sqrt()

◆ square()

◆ to_double()

◆ to_interval()

◆ unit_part()