CGAL 6.2 - Number Types

Loading...
Searching...
No Matches
List of all members | Related Functions
CGAL::Sqrt_extension< NT, Root, DifferentExtensionComparable, FilterPredicates > Class Template Reference
Reference Manual » Relates Algebraic Extensions

`#include <CGAL/Sqrt_extension.h>`

## Definition

template<typename NT, typename Root, typename DifferentExtensionComparable = Tag_false, typename FilterPredicates = Tag_false>
class CGAL::Sqrt_extension< NT, Root, DifferentExtensionComparable, FilterPredicates >

An instance of this class represents an extension of the type `NT` by one square root of the type `Root`.

`NT` is required to be constructible from `Root`.

`NT` is required to be an `IntegralDomainWithoutDivision`.

`Sqrt_extension` is `RealEmbeddable` if NT is `RealEmbeddable`.

For example, let `Integer` be some type representing \( \mathbb{Z}\), then `Sqrt_extension<Integer,Integer>` is able to represent \( \mathbb{Z}[\sqrt{\mathrm{root}}]\) for some arbitrary Integer \(\mathrm{root}\). \( R[a]\) denotes the extension of a ring \( R\) by an element \( a\). See also: `https://mathworld.wolfram.com/ExtensionRing.html` The value of \(\mathrm{root}\) is set at construction time, or set to zero if it is not specified.

Arithmetic operations among different extensions, say \( \mathbb{Z}[\sqrt{a}]\) and \( \mathbb{Z}[\sqrt{b}]\), are not supported. The result would be in \( \mathbb{Z}[\sqrt{a},\sqrt{b}]\), which is not representable by `Sqrt_extension<Integer,Integer>`.

Attention
  The user is responsible to check that arithmetic operations are carried out for elements from the same extensions only. This is not tested by `Sqrt_extension` for efficiency reasons. A violation of the precondition leads to undefined behavior.

Be aware that for efficiency reasons the given \(\mathrm{root}\) is stored as it is given to the constructor. In particular, an extension by a square root of a square is considered as an extension.

Since elements of `Sqrt_extension` that lie in different extensions are not interoperable with respect to any arithmetic operations, the full value range of `Sqrt_extension` does not represent an algebraic structure. However, each subset of the value range that represents the extension of NT by a particular square root is a valid algebraic structure, since this subset is closed under all provided arithmetic operations. From there, `Sqrt_extension` can be used as if it were a model of an algebraic structure concept, with the following correspondence:

NT | `Sqrt_extension`
`IntegralDomainWithoutDivision` | `IntegralDomainWithoutDivision`
`IntegralDomain` | `IntegralDomain`
`UniqueFactorizationDomain` | `IntegralDomain`
`EuclideanRing` | `IntegralDomain`
`Field` | `Field`

The extension of a `UniqueFactorizationDomain` or `EuclideanRing` is just an `IntegralDomain`, since the extension in general destroys the unique factorization property. For instance consider \( \mathbb{Z}[\sqrt{10}]\), the extension of \( \mathbb{Z}\) by \( \sqrt{10}\): in \( \mathbb{Z}[\sqrt{10}]\) the element 10 has two different factorizations \( \sqrt{10} \cdot \sqrt{10}\) and \( 2 \cdot 5\). In particular, the factorization is not unique.

If `NT` is a model of `RealEmbeddable` the type `Sqrt_extension` is also considered as `RealEmbeddable`. However, by default it is not allowed to compare values from different extensions for efficiency reasons. In case such a comparison becomes necessary, use the member function compare with the according Boolean flag. If such a comparison is a very frequent case, override the default of `DifferentExtensionComparable` by giving `CGAL::Tag_true` as third template parameter. This effects the behavior of compare functions as well as the compare operators.

The fourth template argument, `FilterPredicates`, triggers an internal filter that may speed up comparisons and sign computations. In case `FilterPredicates` is set to `CGAL::Tag_true` the type first computes a double interval containing the represented number and tries to perform the comparison or sign computation using this interval. Once computed, this interval is stored by the corresponding `Sqrt_extension` object for further usage. Note that this internal filter is switched off by default, since it may conflict with other filtering methods, such as `Lazy_exact_nt<Sqrt_extension>`.

In case `NT` is not `RealEmbeddable`, `DifferentExtensionComparable` as well as `FilterPredicates` have no effect.

Is model of
  `Assignable`
  `CopyConstructible`
  `DefaultConstructible`
  `EqualityComparable`
  `ImplicitInteroperable` with `int`
  `ImplicitInteroperable` with `NT`
  `Fraction` if NT is a `Fraction`
  `RootOf_2`

See also
  `IntegralDomainWithoutDivision`
  `IntegralDomain`
  `Field`
  `RealEmbeddable`
  `CGAL::Tag_true`
  `CGAL::Tag_false`

## Related Functions
(Note that these are not member functions.)
Sqrt_extension | operator+ (const Sqrt_extension &a, const Sqrt_extension &b)
Sqrt_extension | operator- (const Sqrt_extension &a, const Sqrt_extension &b)
Sqrt_extension | operator* (const Sqrt_extension &a, const Sqrt_extension &b)
Sqrt_extension | operator/ (const Sqrt_extension &a, const Sqrt_extension &b)
bool | operator== (const Sqrt_extension &a, const Sqrt_extension &b)
bool | operator!= (const Sqrt_extension &a, const Sqrt_extension &b)
bool | operator< (const Sqrt_extension &a, const Sqrt_extension &b)
bool | operator<= (const Sqrt_extension &a, const Sqrt_extension &b)
bool | operator> (const Sqrt_extension &a, const Sqrt_extension &b)
bool | operator>= (const Sqrt_extension &a, const Sqrt_extension &b)
std::ostream & | operator<< (std::ostream &os, const Sqrt_extension< NT, Root > &ext)
| writes `ext` to ostream `os`.
std::istream & | operator>> (std::istream &is, const Sqrt_extension< NT, Root > &ext)
| reads `ext` from istream `is` in format `EXT[a0,a1,root]`, the output format in mode `CGAL::IO::ASCII`

## Creation
| Sqrt_extension ()
| Introduces a variable `ext` initialized with 0.
| Sqrt_extension (const Sqrt_extension &x)
| Copy constructor.
| Sqrt_extension (const int &i)
| Introduces a variable `ext` initialized with \( i\).
| Sqrt_extension (const NT &x)
| Introduces a variable `ext` initialized with \( x\).
template<class NTX >
| Sqrt_extension (const NTX &x)
| Introduces a variable `ext` initialized with \( x\).
| Sqrt_extension (int a0, int a1, int r)
| Constructor from int: `ext` \( = a0 +a1 \cdot sqrt(r)\).
| Sqrt_extension (NT a0, NT a1, Root r)
| General constructor: `ext` \( = a0 + a1 \cdot sqrt(r)\).

## Operations
An object of type `Sqrt_extension` represent an expression of the form: \( a0 + a1 \sqrt(\mathrm{root}) \).
const NT & | a0 () const
| Const access operator for a0.
const NT & | a1 () const
| Const access operator for a1.
const Root & | root () const
| Const access operator for root.
bool | is_extended () const
| Returns `true` in case root of `ext` is not zero.
void | simplify ()
| Simplifies the representation, in particular \(\mathrm{root}\) is set to zero if \( a1\) is zero, that is, `ext` becomes not extended.
bool | is_zero () const
| returns `true` if `ext` represents the value zero.
CGAL::Sign | sign () const
| Determines the sign of `ext` by (repeated) squaring.
Sqrt_extension | abs () const
| returns the absolute value of `ext`.
CGAL::Comparison_result | compare (const Sqrt_extension &y, bool in_same_extension=!DifferentExtensionComparable::value) const
| Compares `ext` with y.
Sqrt_extension & | operator+= (const Sqrt_extension &a)
Sqrt_extension & | operator-= (const Sqrt_extension &a)
Sqrt_extension & | operator*= (const Sqrt_extension &a)
Sqrt_extension & | operator/= (const Sqrt_extension &a)

## Constructor & Destructor Documentation

## ◆ Sqrt_extension() [1/3]

template<typename NT , typename Root , typename DifferentExtensionComparable = Tag_false, typename FilterPredicates = Tag_false>
template<class NTX >

CGAL::Sqrt_extension< NT, Root, DifferentExtensionComparable, FilterPredicates >::Sqrt_extension | ( | const NTX & | x | ) |
| explicit

Introduces a variable `ext` initialized with \( x\).

Precondition
  NT must constructible from NTX

## ◆ Sqrt_extension() [2/3]

template<typename NT , typename Root , typename DifferentExtensionComparable = Tag_false, typename FilterPredicates = Tag_false>

CGAL::Sqrt_extension< NT, Root, DifferentExtensionComparable, FilterPredicates >::Sqrt_extension | ( | int | a0,
|  | int | a1,
|  | int | r
| ) |  |

Constructor from int: `ext` \( = a0 +a1 \cdot sqrt(r)\).

Precondition
  \( r \neq0\)

## ◆ Sqrt_extension() [3/3]

template<typename NT , typename Root , typename DifferentExtensionComparable = Tag_false, typename FilterPredicates = Tag_false>

CGAL::Sqrt_extension< NT, Root, DifferentExtensionComparable, FilterPredicates >::Sqrt_extension | ( | NT | a0,
|  | NT | a1,
|  | Root | r
| ) |  |

General constructor: `ext` \( = a0 + a1 \cdot sqrt(r)\).

Precondition
  \( r \neq0\)

## Member Function Documentation

## ◆ abs()

template<typename NT , typename Root , typename DifferentExtensionComparable = Tag_false, typename FilterPredicates = Tag_false>

Sqrt_extension CGAL::Sqrt_extension< NT, Root, DifferentExtensionComparable, FilterPredicates >::abs | ( |  | ) | const

returns the absolute value of `ext`.

Precondition
  `Sqrt_extension` is `RealEmbeddable`.

## ◆ compare()

template<typename NT , typename Root , typename DifferentExtensionComparable = Tag_false, typename FilterPredicates = Tag_false>

CGAL::Comparison_result CGAL::Sqrt_extension< NT, Root, DifferentExtensionComparable, FilterPredicates >::compare | ( | const Sqrt_extension< NT, Root, DifferentExtensionComparable, FilterPredicates > & | y,
|  | bool | in_same_extension = `!DifferentExtensionComparable::value`
| ) |  | const

Compares `ext` with y.

The optional bool `in_same_extension` indicates whether `ext` and \( y\) are in the same extension of NT.

## ◆ is_extended()

template<typename NT , typename Root , typename DifferentExtensionComparable = Tag_false, typename FilterPredicates = Tag_false>

bool CGAL::Sqrt_extension< NT, Root, DifferentExtensionComparable, FilterPredicates >::is_extended | ( |  | ) | const

Returns `true` in case root of `ext` is not zero.

Note that \( a1 == 0 \) does not imply \( \mathrm{root} == 0\).

## ◆ operator*=()

template<typename NT , typename Root , typename DifferentExtensionComparable = Tag_false, typename FilterPredicates = Tag_false>

Sqrt_extension & CGAL::Sqrt_extension< NT, Root, DifferentExtensionComparable, FilterPredicates >::operator*= | ( | const Sqrt_extension< NT, Root, DifferentExtensionComparable, FilterPredicates > & | a | ) |

Precondition
  `(this->root()==0 or a.root()==0 or this->root() == a.root())`

## ◆ operator+=()

template<typename NT , typename Root , typename DifferentExtensionComparable = Tag_false, typename FilterPredicates = Tag_false>

Sqrt_extension & CGAL::Sqrt_extension< NT, Root, DifferentExtensionComparable, FilterPredicates >::operator+= | ( | const Sqrt_extension< NT, Root, DifferentExtensionComparable, FilterPredicates > & | a | ) |

Precondition
  `(this->root()==0 or a.root()==0 or this->root() == a.root())`

## ◆ operator-=()

template<typename NT , typename Root , typename DifferentExtensionComparable = Tag_false, typename FilterPredicates = Tag_false>

Sqrt_extension & CGAL::Sqrt_extension< NT, Root, DifferentExtensionComparable, FilterPredicates >::operator-= | ( | const Sqrt_extension< NT, Root, DifferentExtensionComparable, FilterPredicates > & | a | ) |

Precondition
  `(this->root()==0 or a.root()==0 or this->root() == a.root())`

## ◆ operator/=()

template<typename NT , typename Root , typename DifferentExtensionComparable = Tag_false, typename FilterPredicates = Tag_false>

Sqrt_extension & CGAL::Sqrt_extension< NT, Root, DifferentExtensionComparable, FilterPredicates >::operator/= | ( | const Sqrt_extension< NT, Root, DifferentExtensionComparable, FilterPredicates > & | a | ) |

Precondition
  `(this->root()==0 or a.root()==0 or this->root() == a.root())`

In case `NT` is only an `IntegralDomain` operator/ implements integral division. In case `NT` is a `Field` operator/ implements the field division.

## ◆ sign()

template<typename NT , typename Root , typename DifferentExtensionComparable = Tag_false, typename FilterPredicates = Tag_false>

CGAL::Sign CGAL::Sqrt_extension< NT, Root, DifferentExtensionComparable, FilterPredicates >::sign | ( |  | ) | const

Determines the sign of `ext` by (repeated) squaring.

Precondition
  `Sqrt_extension` is `RealEmbeddable`.

## ◆ simplify()

template<typename NT , typename Root , typename DifferentExtensionComparable = Tag_false, typename FilterPredicates = Tag_false>

void CGAL::Sqrt_extension< NT, Root, DifferentExtensionComparable, FilterPredicates >::simplify | ( |  | ) |

Simplifies the representation, in particular \(\mathrm{root}\) is set to zero if \( a1\) is zero, that is, `ext` becomes not extended.

Moreover, it propagates the simplify command to members of `ext`. see also: `AlgebraicStructureTraits::Simplify`.

## Friends And Related Function Documentation

## ◆ operator!=()

template<typename NT , typename Root , typename DifferentExtensionComparable = Tag_false, typename FilterPredicates = Tag_false>

bool operator!= | ( | const Sqrt_extension< NT, Root, DifferentExtensionComparable, FilterPredicates > & | a,
|  | const Sqrt_extension< NT, Root, DifferentExtensionComparable, FilterPredicates > & | b
| ) |  |
| related

Precondition
  `(a.root()==0 or b.root()==0 or a.root() == b.root())`

## ◆ operator*()

template<typename NT , typename Root , typename DifferentExtensionComparable = Tag_false, typename FilterPredicates = Tag_false>

Sqrt_extension operator* | ( | const Sqrt_extension< NT, Root, DifferentExtensionComparable, FilterPredicates > & | a,
|  | const Sqrt_extension< NT, Root, DifferentExtensionComparable, FilterPredicates > & | b
| ) |  |
| related

Precondition
  `(a.root()==0 or b.root()==0 or a.root() == b.root())`

## ◆ operator+()

template<typename NT , typename Root , typename DifferentExtensionComparable = Tag_false, typename FilterPredicates = Tag_false>

Sqrt_extension operator+ | ( | const Sqrt_extension< NT, Root, DifferentExtensionComparable, FilterPredicates > & | a,
|  | const Sqrt_extension< NT, Root, DifferentExtensionComparable, FilterPredicates > & | b
| ) |  |
| related

Precondition
  `(a.root()==0 or b.root()==0 or a.root() == b.root())`

## ◆ operator-()

template<typename NT , typename Root , typename DifferentExtensionComparable = Tag_false, typename FilterPredicates = Tag_false>

Sqrt_extension operator- | ( | const Sqrt_extension< NT, Root, DifferentExtensionComparable, FilterPredicates > & | a,
|  | const Sqrt_extension< NT, Root, DifferentExtensionComparable, FilterPredicates > & | b
| ) |  |
| related

Precondition
  `(a.root()==0 or b.root()==0 or a.root() == b.root())`

## ◆ operator/()

template<typename NT , typename Root , typename DifferentExtensionComparable = Tag_false, typename FilterPredicates = Tag_false>

Sqrt_extension operator/ | ( | const Sqrt_extension< NT, Root, DifferentExtensionComparable, FilterPredicates > & | a,
|  | const Sqrt_extension< NT, Root, DifferentExtensionComparable, FilterPredicates > & | b
| ) |  |
| related

Precondition
  `(a.root()==0 or b.root()==0 or a.root() == b.root())`

In case `NT` is only an `IntegralDomain` operator/ implements integral division. In case `NT` is a `Field` operator/ implements the field division.

## ◆ operator<()

template<typename NT , typename Root , typename DifferentExtensionComparable = Tag_false, typename FilterPredicates = Tag_false>

bool operator< | ( | const Sqrt_extension< NT, Root, DifferentExtensionComparable, FilterPredicates > & | a,
|  | const Sqrt_extension< NT, Root, DifferentExtensionComparable, FilterPredicates > & | b
| ) |  |
| related

Precondition
  `(a.root()==0 or b.root()==0 or a.root() == b.root())`

Attention
  Only exists when `Sqrt_extension` is `RealEmbeddable`.

## ◆ operator<<()

template<typename NT , typename Root , typename DifferentExtensionComparable = Tag_false, typename FilterPredicates = Tag_false>

std::ostream & operator<< | ( | std::ostream & | os,
|  | const Sqrt_extension< NT, Root > & | ext
| ) |  |
| related

writes `ext` to ostream `os`.

The format depends on the `CGAL::IO::MODE` of `os`.

In case the mode is `CGAL::IO::ASCII` the format is `EXT[a0,a1,root]`.

In case the mode is `CGAL::IO::PRETTY` the format is human readable.

Attention
  `operator>>` must be defined for `Root` and `NT`.

## ◆ operator<=()

template<typename NT , typename Root , typename DifferentExtensionComparable = Tag_false, typename FilterPredicates = Tag_false>

bool operator<= | ( | const Sqrt_extension< NT, Root, DifferentExtensionComparable, FilterPredicates > & | a,
|  | const Sqrt_extension< NT, Root, DifferentExtensionComparable, FilterPredicates > & | b
| ) |  |
| related

Precondition
  `(a.root()==0 or b.root()==0 or a.root() == b.root())`

Attention
  Only exists when `Sqrt_extension` is `RealEmbeddable`.

## ◆ operator==()

template<typename NT , typename Root , typename DifferentExtensionComparable = Tag_false, typename FilterPredicates = Tag_false>

bool operator== | ( | const Sqrt_extension< NT, Root, DifferentExtensionComparable, FilterPredicates > & | a,
|  | const Sqrt_extension< NT, Root, DifferentExtensionComparable, FilterPredicates > & | b
| ) |  |
| related

Precondition
  `(a.root()==0 or b.root()==0 or a.root() == b.root())`

## ◆ operator>()

template<typename NT , typename Root , typename DifferentExtensionComparable = Tag_false, typename FilterPredicates = Tag_false>

bool operator> | ( | const Sqrt_extension< NT, Root, DifferentExtensionComparable, FilterPredicates > & | a,
|  | const Sqrt_extension< NT, Root, DifferentExtensionComparable, FilterPredicates > & | b
| ) |  |
| related

Precondition
  `(a.root()==0 or b.root()==0 or a.root() == b.root())`

Attention
  Only exists when `Sqrt_extension` is `RealEmbeddable`.

## ◆ operator>=()

template<typename NT , typename Root , typename DifferentExtensionComparable = Tag_false, typename FilterPredicates = Tag_false>

bool operator>= | ( | const Sqrt_extension< NT, Root, DifferentExtensionComparable, FilterPredicates > & | a,
|  | const Sqrt_extension< NT, Root, DifferentExtensionComparable, FilterPredicates > & | b
| ) |  |
| related

Precondition
  `(a.root()==0 or b.root()==0 or a.root() == b.root())`

Attention
  Only exists when `Sqrt_extension` is `RealEmbeddable`.

## ◆ operator>>()

template<typename NT , typename Root , typename DifferentExtensionComparable = Tag_false, typename FilterPredicates = Tag_false>

std::istream & operator>> | ( | std::istream & | is,
|  | const Sqrt_extension< NT, Root > & | ext
| ) |  |
| related

reads `ext` from istream `is` in format `EXT[a0,a1,root]`, the output format in mode `CGAL::IO::ASCII`

Attention
  `operator<<` must be defined exist for `Root` and `NT`.