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< Integer >	Polynomial
	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

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

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

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.