CGAL 6.0.1 - 2D Arrangements
Loading...
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.

See also
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.
 

Member Function Documentation

◆ 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
polyThe input polynomial.
x_minThe left bound of the interval.
x_maxThe right bound of the interval.
oiThe 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
polyThe input polynomial.
oiThe 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
coeffsThe coefficients of the input polynomial.
degreeThe 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
coeffsThe coefficients of the input polynomial.
degreeThe degree of the input polynomial.
polyOutput: The resulting polynomial with integer coefficients.
poly_denomOutput: 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_coeffsThe coefficients of the input numerator polynomial.
p_degreeThe degree of the input numerator polynomial.
q_coeffsThe coefficients of the input denominator polynomial.
q_degreeThe degree of the input denominator polynomial.
p_polyOutput: The resulting numerator polynomial with integer coefficients.
q_polyOutput: 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
zThe 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
qA 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
beginThe begin iterator of the rational coefficients input container.
endThe past-the-end iterator of the rational coefficients input container.
oiThe 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
qThe 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
polyThe 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_aThe first polynomial \(A(x)\).
poly_bThe second polynomial \(A(x)\).
remOutput: 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
xThe 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
polyThe polynomial.
xThe 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
qThe 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
x1The first algebraic value.
x2The 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
polyThe polynomial \(P(x)\).
aThe scalar value.
Returns
The scalar multiplication \(a \cdot P(x)\).

◆ solve_quadratic_equation()

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
aThe coefficient of \(x^2\)
bThe coefficient of \(x\)
cThe free term.
oiThe 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
xThe number.
Returns
The square root of x.
Precondition
x is non-negative.