CGAL 6.0 - 2D Arrangements
Searching...
No Matches
CGAL::CORE_algebraic_number_traits Class Reference

#include <CGAL/CORE_algebraic_number_traits.h>

Definition

CORE_algebraic_number_traits is a traits class for CORE's algebraic number types.

Arr_conic_traits_2<RatKernel, AlgKernel, NtTraits>

Types

typedef CORE::BigInt Integer
The integer number type.

typedef CORE::BigRat Rational
The rational number type.

typedef CORE::Polynomial< IntegerPolynomial
The polynomial type.

typedef CORE::Expr Algebraic
The algebraic number type.

Utility Functions

Integer numerator (const Rational &q) const
obtains the numerator of a rational number.

Integer denominator (const Rational &q) const
obtains the denominator of a rational number.

Algebraic convert (const Integer &z) const
converts an integer to an algebraic number.

Algebraic convert (const Rational &q) const
converts a rational number to an algebraic number.

Rational rational_in_interval (const Algebraic &x1, const Algebraic &x2) const
constructs a rational number that lies strictly between two algebraic values.

std::pair< double, double > double_interval (const Algebraic &x) const
obtains a range of double-precision floats that contains the given algebraic number.

template<typename InputIterator , typename OutputIterator >
OutputIterator convert_coefficients (InputIterator begin, InputIterator end, OutputIterator oi) const
converts a sequence of rational coefficients to an equivalent sequence of integer coefficients.

Algebraic sqrt (const Algebraic &x) const
computes the square root of an algebraic number.

template<typename NT , typename OutputIterator >
OutputIterator solve_quadratic_equation (const NT &a, const NT &b, const NT &c, OutputIterator oi) const
computes the roots of a quadratic equations $$a*x^2+ b*x + c = 0$$ with integer coefficients, and inserts them into an output container given through an output iterator.

Polynomial construct_polynomial (const Integer *coeffs, unsigned int degree) const
constructs a polynomial with integer coefficients.

bool construct_polynomial (const Rational *coeffs, unsigned int degree, Polynomial &poly, Integer &poly_denom) const
constructs a polynomial with integer coefficients given rational coefficients.

bool construct_polynomials (const Rational *p_coeffs, unsigned int p_degree, const Rational *q_coeffs, unsigned int q_degree, Polynomial &p_poly, Polynomial &q_poly) const
constructs two polynomials with integer coefficients such that $$P(x)/Q(x)$$ is a rational function equivalent to the one represented by the two given vectors of rational coefficients.

int degree (const Polynomial &poly) const
Compute the degree of a polynomial.

template<typename NT >
NT evaluate_at (const Polynomial &poly, NT &x) const
evaluates a polynomial at a given $$x$$-value.

Polynomial derive (const Polynomial &poly) const
computes the derivative of the given polynomial.

Polynomial scale (const Polynomial &poly, const Integer &a) const
multiplies a polynomial by some scalar coefficient.

Polynomial divide (const Polynomial &poly_a, const Polynomial &poly_b, Polynomial &rem) const
performs "long division" of two polynomials: Given $$A(x)$$ and $$B(x)$$ compute two polynomials $$Q(x)$$ and $$R(x)$$ such that: $$A(x) = Q(x) \cdot B(x) + R(x)$$ and $$R(x)$$ has minimal degree.

template<typename OutputIterator >
OutputIterator compute_polynomial_roots (const Polynomial &poly, OutputIterator oi) const
computes the real-valued roots of a polynomial with integer coefficients, and inserts them in ascending order into an output container given through an output iterator.

template<typename OutputIterator >
OutputIterator compute_polynomial_roots (const Polynomial &poly, double x_min, double x_max, OutputIterator oi) const
computes the real-valued roots of a polynomial with integer coefficients within a given interval, and inserts them in ascending order into an output container given through an output iterator.

◆ compute_polynomial_roots() [1/2]

template<typename OutputIterator >
 OutputIterator CGAL::CORE_algebraic_number_traits::compute_polynomial_roots ( const Polynomial & poly, double x_min, double x_max, OutputIterator oi ) const

computes the real-valued roots of a polynomial with integer coefficients within a given interval, and inserts them in ascending order into an output container given through an output iterator.

Parameters
 poly The input polynomial. x_min The left bound of the interval. x_max The right bound of the interval. oi The output iterator of the output container of the real-valued root of the polynomial.
Returns
The past-the-end iterator of the output container.
Precondition
Dereferencing oi must yield an object convertible to Algebraic.

◆ compute_polynomial_roots() [2/2]

template<typename OutputIterator >
 OutputIterator CGAL::CORE_algebraic_number_traits::compute_polynomial_roots ( const Polynomial & poly, OutputIterator oi ) const

computes the real-valued roots of a polynomial with integer coefficients, and inserts them in ascending order into an output container given through an output iterator.

Parameters
 poly The input polynomial. oi The output iterator of the output container of real-valued root of the polynomial.
Returns
The past-the-end iterator of the output container.
Precondition
Dereferencing oi must yield an object convertible to Algebraic.

◆ construct_polynomial() [1/2]

 Polynomial CGAL::CORE_algebraic_number_traits::construct_polynomial ( const Integer * coeffs, unsigned int degree ) const

constructs a polynomial with integer coefficients.

Parameters
 coeffs The coefficients of the input polynomial. degree The degree of the input polynomial.
Returns
The polynomial.

◆ construct_polynomial() [2/2]

 bool CGAL::CORE_algebraic_number_traits::construct_polynomial ( const Rational * coeffs, unsigned int degree, Polynomial & poly, Integer & poly_denom ) const

constructs a polynomial with integer coefficients given rational coefficients.

Parameters
 coeffs The coefficients of the input polynomial. degree The degree of the input polynomial. poly Output: The resulting polynomial with integer coefficients. poly_denom Output: The denominator for the polynomial.
Returns
Whether this polynomial is non-zero (false if the polynomial is zero).

◆ construct_polynomials()

 bool CGAL::CORE_algebraic_number_traits::construct_polynomials ( const Rational * p_coeffs, unsigned int p_degree, const Rational * q_coeffs, unsigned int q_degree, Polynomial & p_poly, Polynomial & q_poly ) const

constructs two polynomials with integer coefficients such that $$P(x)/Q(x)$$ is a rational function equivalent to the one represented by the two given vectors of rational coefficients.

It is guaranteed that the GCD of $$P(x)$$ and $$Q(x)$$ is trivial.

Parameters
 p_coeffs The coefficients of the input numerator polynomial. p_degree The degree of the input numerator polynomial. q_coeffs The coefficients of the input denominator polynomial. q_degree The degree of the input denominator polynomial. p_poly Output: The resulting numerator polynomial with integer coefficients. q_poly Output: The resulting denominator polynomial with integer coefficients.
Returns
true on success; false if the denominator is 0.

◆ convert() [1/2]

 Algebraic CGAL::CORE_algebraic_number_traits::convert ( const Integer & z ) const

converts an integer to an algebraic number.

Parameters
 z The integer.
Returns
The algebraic number equivalent to z.

◆ convert() [2/2]

 Algebraic CGAL::CORE_algebraic_number_traits::convert ( const Rational & q ) const

converts a rational number to an algebraic number.

Parameters
 q A rational number.
Returns
The algebraic number equivalent to q.

◆ convert_coefficients()

template<typename InputIterator , typename OutputIterator >
 OutputIterator CGAL::CORE_algebraic_number_traits::convert_coefficients ( InputIterator begin, InputIterator end, OutputIterator oi ) const

converts a sequence of rational coefficients to an equivalent sequence of integer coefficients.

If the input coefficients are $$q(1),\ldots,q(k)$$, where $$q(i) = n(i)/d(i)$$, then the output coefficients will be of the form: $$a(i) = \frac{n(i) \cdot \mathrm{lcm}(d(1),\ldots,d(k))}{d(i) \cdot \mathrm{gcd}(n(1),\ldots, n(k))}$$. It inserts the output sequence into an output container given through an output iterator.

Parameters
 begin The begin iterator of the rational coefficients input container. end The past-the-end iterator of the rational coefficients input container. oi The output iterator of the integer coefficients output container.
Returns
The past-the-end iterator of the output container.
Precondition
The value type of InputIterator is Rational.
Dereferencing oi must yield an object convertible to Integer.

◆ denominator()

 Integer CGAL::CORE_algebraic_number_traits::denominator ( const Rational & q ) const

obtains the denominator of a rational number.

Parameters
 q The rational number.
Returns
The denominator of q.

◆ derive()

 Polynomial CGAL::CORE_algebraic_number_traits::derive ( const Polynomial & poly ) const

computes the derivative of the given polynomial.

Parameters
 poly The polynomial $$p(x)$$.
Returns
The derivative $$p'(x)$$.

◆ divide()

 Polynomial CGAL::CORE_algebraic_number_traits::divide ( const Polynomial & poly_a, const Polynomial & poly_b, Polynomial & rem ) const

performs "long division" of two polynomials: Given $$A(x)$$ and $$B(x)$$ compute two polynomials $$Q(x)$$ and $$R(x)$$ such that: $$A(x) = Q(x) \cdot B(x) + R(x)$$ and $$R(x)$$ has minimal degree.

Parameters
 poly_a The first polynomial $$A(x)$$. poly_b The second polynomial $$A(x)$$. rem Output: The remainder polynomial $$R(x)$$.
Returns
The quontient polynomial $$Q(x)$$.

◆ double_interval()

 std::pair< double, double > CGAL::CORE_algebraic_number_traits::double_interval ( const Algebraic & x ) const

obtains a range of double-precision floats that contains the given algebraic number.

Parameters
 x The given number.
Returns
The range of double-precision floats that contain x.

◆ evaluate_at()

template<typename NT >
 NT CGAL::CORE_algebraic_number_traits::evaluate_at ( const Polynomial & poly, NT & x ) const

evaluates a polynomial at a given $$x$$-value.

Parameters
 poly The polynomial. x The value to evaluate at.
Returns
The value of the polynomial at x.

◆ numerator()

 Integer CGAL::CORE_algebraic_number_traits::numerator ( const Rational & q ) const

obtains the numerator of a rational number.

Parameters
 q The rational number.
Returns
The numerator of q.

◆ rational_in_interval()

 Rational CGAL::CORE_algebraic_number_traits::rational_in_interval ( const Algebraic & x1, const Algebraic & x2 ) const

constructs a rational number that lies strictly between two algebraic values.

Parameters
 x1 The first algebraic value. x2 The second algebraic value.
Precondition
The two values are not equal.
Returns
The rational number that lies in the open interval (x1, x2).

◆ scale()

 Polynomial CGAL::CORE_algebraic_number_traits::scale ( const Polynomial & poly, const Integer & a ) const

multiplies a polynomial by some scalar coefficient.

Parameters
 poly The polynomial $$P(x)$$. a The scalar value.
Returns
The scalar multiplication $$a \cdot P(x)$$.

template<typename NT , typename OutputIterator >
 OutputIterator CGAL::CORE_algebraic_number_traits::solve_quadratic_equation ( const NT & a, const NT & b, const NT & c, OutputIterator oi ) const

computes the roots of a quadratic equations $$a*x^2+ b*x + c = 0$$ with integer coefficients, and inserts them into an output container given through an output iterator.

Parameters
 a The coefficient of $$x^2$$ b The coefficient of $$x$$ c The free term. oi The output iterator of the output container of real-valued solutions of the quadratic equation.
Returns
The past-the-end iterator of the output container.
Precondition
Dereferencing oi must yield an object convertible to Algebraic.

◆ sqrt()

 Algebraic CGAL::CORE_algebraic_number_traits::sqrt ( const Algebraic & x ) const

computes the square root of an algebraic number.

Parameters
 x The number.
Returns
The square root of x.
Precondition
x is non-negative.