CGAL 6.1.1 - Algebraic Foundations

Loading...
Searching...
No Matches
Modules | Classes | Functions
Reference Manual

##

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