Univariate polynomial over a generic coefficient ring. More...

#include <tpl_polynomial.H>

Collaboration diagram for Aleph::Gen_Polynomial< Coefficient >:

Classes
struct	SfdTerm
	Square-free decomposition term: factor and multiplicity. More...

struct	Xgcd_Result
	Extended GCD: computes g, s, t such that \(sa + tb = g\). More...

Public Types
using	Coeff = Coefficient

Public Member Functions
	Gen_Polynomial ()=default
	Default constructor: the zero polynomial.

	Gen_Polynomial (const Coefficient &c)
	Constant polynomial \(p(x) = c\).

	Gen_Polynomial (const Coefficient &c, size_t exp)
	Monomial \(c \cdot x^e\).

	Gen_Polynomial (std::initializer_list< Coefficient > il)
	Dense construction from initializer list.

	Gen_Polynomial (const DynList< Coefficient > &l)
	Dense construction from DynList.

	Gen_Polynomial (const DynList< std::pair< size_t, Coefficient > > &term_list)
	Sparse construction from a list of (exponent, coefficient) pairs.

bool	is_zero () const noexcept
	True if this is the zero polynomial.

size_t	degree () const noexcept
	Degree of the polynomial.

size_t	num_terms () const noexcept
	Number of non-zero terms.

bool	is_constant () const noexcept
	True if constant or zero.

bool	is_monomial () const noexcept
	True if exactly one non-zero term.

bool	is_monic () const noexcept
	True if leading coefficient equals 1.

Coefficient	operator[] (size_t exp) const
	Coefficient at exponent `exp` (0 if absent).

Coefficient	leading_coeff () const noexcept
	Leading coefficient (of the highest-degree term).

bool	has_term (size_t exp) const noexcept
	True if there is a non-zero coefficient at `exp`.

Coefficient	horner_eval (const Coefficient &x) const
	Evaluate \(p(x)\) using gap-aware Horner's method.

Coefficient	sparse_eval (const Coefficient &x) const
	Evaluate \(p(x)\) using sparse evaluation.

Coefficient	eval (const Coefficient &x) const
	Evaluate \(p(x)\) with adaptive strategy.

Coefficient	operator() (const Coefficient &x) const
	Syntactic sugar: `p(x)` calls eval.

DynList< Coefficient >	multi_eval (const DynList< Coefficient > &points) const
	Evaluate at multiple points.

Gen_Polynomial	operator- () const
	Unary negation.

Gen_Polynomial	operator+ (const Gen_Polynomial &q) const
	Polynomial addition.

Gen_Polynomial &	operator+= (const Gen_Polynomial &q)
	In-place addition.

Gen_Polynomial	operator+ (const Coefficient &c) const
	Add a scalar constant term.

Gen_Polynomial &	operator+= (const Coefficient &c)
	In-place addition of a scalar constant term.

Gen_Polynomial	operator- (const Gen_Polynomial &q) const
	Polynomial subtraction.

Gen_Polynomial &	operator-= (const Gen_Polynomial &q)
	In-place subtraction.

Gen_Polynomial	operator- (const Coefficient &c) const
	Subtract a scalar constant term.

Gen_Polynomial &	operator-= (const Coefficient &c)
	In-place subtraction of a scalar constant term.

Gen_Polynomial	operator* (const Gen_Polynomial &q) const
	Polynomial multiplication.

Gen_Polynomial &	operator*= (const Gen_Polynomial &q)
	In-place multiplication.

Gen_Polynomial	operator* (const Coefficient &s) const
	Multiply by a scalar.

Gen_Polynomial &	operator*= (const Coefficient &s)
	In-place scalar multiplication.

Gen_Polynomial	operator/ (const Coefficient &s) const
	Divide by a scalar.

Gen_Polynomial &	operator/= (const Coefficient &s)
	In-place scalar division.

std::pair< Gen_Polynomial, Gen_Polynomial >	divmod (const Gen_Polynomial &d) const
	Polynomial long division: returns (quotient, remainder).

Gen_Polynomial	operator/ (const Gen_Polynomial &d) const
	Polynomial quotient.

Gen_Polynomial	operator% (const Gen_Polynomial &d) const
	Polynomial remainder.

Gen_Polynomial &	operator/= (const Gen_Polynomial &d)
	In-place polynomial quotient.

Gen_Polynomial &	operator%= (const Gen_Polynomial &d)
	In-place polynomial remainder.

Gen_Polynomial	derivative () const
	Formal derivative \(p'(x)\).

Gen_Polynomial	nth_derivative (size_t n) const
	\(n\)-th derivative \(p^{(n)}(x)\).

Gen_Polynomial	integral (const Coefficient &C=Coefficient{}) const
	Formal indefinite integral with constant of integration.

Coefficient	definite_integral (const Coefficient &a, const Coefficient &b) const
	Definite integral \(\int_a^b p(x)\,dx\).

Gen_Polynomial	compose (const Gen_Polynomial &q) const
	Composition \(p(q(x))\).

Gen_Polynomial	pow (size_t n) const
	Exponentiation \(p(x)^n\) by repeated squaring.

std::pair< Gen_Polynomial, Gen_Polynomial >	pseudo_divmod (const Gen_Polynomial &d) const
	Pseudo-division for non-field coefficient types.

Gen_Polynomial	to_monic () const
	Make monic: divide by leading coefficient.

Gen_Polynomial	reverse () const
	Reciprocal polynomial: \(x^d \cdot p(1/x)\).

Gen_Polynomial	negate_arg () const
	Argument negation: \(p(-x)\).

Gen_Polynomial	shift (const Coefficient &k) const
	Taylor shift: \(p(x + k)\).

Gen_Polynomial	shift_up (size_t k) const
	Multiply by \(x^k\) (shift exponents up).

Gen_Polynomial	shift_down (size_t k) const
	Divide by \(x^k\) (shift exponents down).

Gen_Polynomial	truncate (size_t n) const
	Truncate to degree less than `n`.

Array< Coefficient >	to_dense () const
	Dense coefficient vector.

Gen_Polynomial	square_free () const
	Square-free part: \(p / \gcd(p, p')\).

Coefficient	cauchy_bound () const
	Cauchy upper bound on absolute value of roots.

size_t	sign_variations () const
	Count sign changes in the coefficient sequence.

DynList< Gen_Polynomial >	sturm_chain () const
	Sturm sequence of this polynomial.

size_t	count_real_roots (const Coefficient &a, const Coefficient &b) const
	Count distinct real roots in \([a, b]\) via Sturm's theorem.

size_t	count_all_real_roots () const
	Total number of distinct real roots.

Coefficient	bisect_root (Coefficient a, Coefficient b, Coefficient tol=Coefficient(1e-12), size_t max_iter=200) const
	Find a root by bisection in \([a, b]\).

Coefficient	newton_root (Coefficient x0, Coefficient tol=Coefficient(1e-12), size_t max_iter=100) const
	Find a root by Newton-Raphson iteration.

bool	operator== (const Gen_Polynomial &q) const noexcept
	Equality comparison.

bool	operator!= (const Gen_Polynomial &q) const noexcept
	Inequality comparison.

template<class Op >
void	for_each_term (Op &&op) const
	Iterate over non-zero terms in ascending exponent order.

DynList< std::pair< size_t, Coefficient > >	terms_list () const
	All non-zero terms as a sorted list of (exponent, coefficient).

DynList< size_t >	exponents () const
	All exponents with non-zero coefficients (sorted ascending).

DynList< Coefficient >	coefficients () const
	All non-zero coefficients in ascending exponent order.

std::string	to_str (const std::string &var="x") const
	Human-readable string representation.

Coefficient	get_coeff (size_t exp) const noexcept
	Coefficient accessor (read-only at exponent).

void	set_coeff (size_t exp, const Coefficient &c)
	Set coefficient at exponent; removes entry if zero.

Coefficient	content () const
	Content: GCD of all coefficients.

Gen_Polynomial	primitive_part () const
	Primitive part: polynomial divided by its content.

DynList< SfdTerm >	yun_sfd () const
	Yun's square-free decomposition (SFD).

double	mignotte_bound () const
	Mignotte bound on integer roots.

DynList< SfdTerm >	factorize () const
	Main factorization over integers.

Static Public Member Functions
static Gen_Polynomial	zero ()
	The zero polynomial.

static Gen_Polynomial	one ()
	The constant polynomial 1.

static Gen_Polynomial	x_to (size_t n)
	The monomial \(x^n\).

static Gen_Polynomial	from_roots (const DynList< Coefficient > &roots)
	Build polynomial from its roots: \(\prod (x - r_i)\).

static Gen_Polynomial	interpolate (const DynList< std::pair< Coefficient, Coefficient > > &points)
	Polynomial interpolation through a set of points.

static Gen_Polynomial	gcd (Gen_Polynomial a, Gen_Polynomial b)
	Greatest common divisor (Euclidean algorithm).

static Xgcd_Result	xgcd (Gen_Polynomial a, Gen_Polynomial b)

static Gen_Polynomial	lcm (const Gen_Polynomial &a, const Gen_Polynomial &b)
	Least common multiple.

static size_t	sturm_sign_changes (const DynList< Gen_Polynomial > &chain, const Coefficient &x)
	Count sign changes in a Sturm chain at a given point.

static Gen_Polynomial	integer_gcd (Gen_Polynomial a, Gen_Polynomial b)
	Polynomial GCD over integers (Euclidean algorithm with primitive parts).

static Gen_Polynomial	_integer_exact_quot (const Gen_Polynomial &a, const Gen_Polynomial &b)
	Integer-safe exact quotient using pseudo-division.

static Gen_Polynomial	reduce_coeffs_mod (const Gen_Polynomial &f, Coefficient mod)

static uint64_t	eval_mod_u64 (const Gen_Polynomial &f, uint64_t x, uint64_t mod)

static Gen_Polynomial	divide_by_monic_linear_mod (const Gen_Polynomial &f, Coefficient root, Coefficient mod)

static DynList< Coefficient >	positive_divisors (Coefficient value)

static bool	try_exact_candidate_division (const Gen_Polynomial &f, const Gen_Polynomial &candidate, Gen_Polynomial &quotient)
	Try exact division but treat inexact integral division as a rejected candidate.

static bool	try_divide_by_linear_factor (const Gen_Polynomial &f, Coefficient a, Coefficient b, Gen_Polynomial &quotient)

static bool	try_extract_rational_linear_factor (const Gen_Polynomial &f, Gen_Polynomial &factor, Gen_Polynomial &quotient)

static bool	try_extract_primitive_quadratic_factor (const Gen_Polynomial &f, Gen_Polynomial &factor, Gen_Polynomial &quotient)
	Try to extract an exact primitive quadratic factor over \(\mathbb{Z}\).

static bool	try_extract_primitive_cubic_factor (const Gen_Polynomial &f, Gen_Polynomial &factor, Gen_Polynomial &quotient)
	Try to extract an exact primitive cubic factor over \(\mathbb{Z}\).

static DynList< Gen_Polynomial >	factor_mod_p (const Gen_Polynomial &f, Coefficient p)
	Factorization over integers mod `p` (trial method).

static DynList< Gen_Polynomial >	hensel_lift (const Gen_Polynomial &f, DynList< Gen_Polynomial > factors, Coefficient p, size_t levels)
	Hensel lifting of modular factors.

Private Types
using	Term = std::pair< size_t, Coefficient >

Private Member Functions
void	remove_zeros ()
	Remove all entries whose coefficient is (approximately) zero.

Coefficient	coeff_at (size_t exp) const
	Read coefficient at exponent (0 if absent).

Coefficient *	coeff_ptr (size_t exp) noexcept
	Pointer to stored coefficient, or null if absent.

const Coefficient *	coeff_ptr (size_t exp) const noexcept
	Pointer to stored coefficient, or null if absent.

void	add_to_coeff (size_t exp, const Coefficient &delta)
	Add a delta to one coefficient, erasing the term if it cancels.

void	add_scaled_shifted (const Gen_Polynomial &src, const Coefficient &scale, size_t shift=0)
	Add `scale` times `src` shifted by `shift` to this polynomial.

void	scale_inplace (const Coefficient &s)
	Multiply every coefficient in place by a scalar.

void	divide_scalar_inplace (const Coefficient &s)
	Divide every coefficient in place by a scalar.

template<class Op >
void	for_each_term_desc (Op &&op) const
	Iterate over non-zero terms in descending exponent order.

Gen_Polynomial	multiply_by_monic_linear (const Coefficient &c) const
	Specialized multiplication by a monic linear factor \(x + c\).

Static Private Member Functions
static constexpr Coefficient	epsilon () noexcept
	Tolerance threshold for floating-point zero detection.

static bool	coeff_is_zero (const Coefficient &c) noexcept
	Test whether a coefficient is (approximately) zero.

Private Attributes
DynMapTree< size_t, Coefficient >	coeffs

Detailed Description

template<typename Coefficient = double>
class Aleph::Gen_Polynomial< Coefficient >

Univariate polynomial over a generic coefficient ring.

Internally stores only non-zero coefficients in a DynMapTree<size_t, Coefficient> mapping exponents to coefficients. The zero polynomial is represented by an empty map.

For floating-point coefficient types, an epsilon-based zero test is used automatically to prevent accumulation of near-zero terms.

Template Parameters

Coefficient Coefficient ring (default double).

Definition at line 166 of file tpl_polynomial.H.

Member Typedef Documentation

◆ Coeff

template<typename Coefficient = double>

using Aleph::Gen_Polynomial< Coefficient >::Coeff = Coefficient

Definition at line 169 of file tpl_polynomial.H.

◆ Term

template<typename Coefficient = double>

using Aleph::Gen_Polynomial< Coefficient >::Term = std::pair<size_t, Coefficient>

private

Definition at line 172 of file tpl_polynomial.H.

Constructor & Destructor Documentation

◆ Gen_Polynomial() [1/6]

template<typename Coefficient = double>

Aleph::Gen_Polynomial< Coefficient >::Gen_Polynomial ( )

default

Default constructor: the zero polynomial.

◆ Gen_Polynomial() [2/6]

template<typename Coefficient = double>

Aleph::Gen_Polynomial< Coefficient >::Gen_Polynomial ( const Coefficient & c )

inlineexplicit

Constant polynomial \(p(x) = c\).

Parameters

[in] c The constant value.

Definition at line 369 of file tpl_polynomial.H.

References Aleph::Gen_Polynomial< Coefficient >::coeff_is_zero(), Aleph::Gen_Polynomial< Coefficient >::coeffs, and Aleph::divide_and_conquer_partition_dp().

◆ Gen_Polynomial() [3/6]

template<typename Coefficient = double>

Aleph::Gen_Polynomial< Coefficient >::Gen_Polynomial	(	const Coefficient &	c,
		size_t	exp
	)

inline

Monomial \(c \cdot x^e\).

Parameters

[in]	c	Coefficient.
[in]	exp	Exponent.

Definition at line 379 of file tpl_polynomial.H.

References Aleph::Gen_Polynomial< Coefficient >::coeff_is_zero(), Aleph::Gen_Polynomial< Coefficient >::coeffs, Aleph::divide_and_conquer_partition_dp(), and exp().

◆ Gen_Polynomial() [4/6]

template<typename Coefficient = double>

Aleph::Gen_Polynomial< Coefficient >::Gen_Polynomial ( std::initializer_list< Coefficient > il )

inline

Dense construction from initializer list.

The list \(\{a_0, a_1, \ldots, a_n\}\) yields \(a_0 + a_1 x + \cdots + a_n x^n\).

Parameters

[in] il Coefficients in ascending exponent order.

Definition at line 392 of file tpl_polynomial.H.

References Aleph::Gen_Polynomial< Coefficient >::coeff_is_zero(), Aleph::Gen_Polynomial< Coefficient >::coeffs, Aleph::divide_and_conquer_partition_dp(), and exp().

◆ Gen_Polynomial() [5/6]

template<typename Coefficient = double>

Aleph::Gen_Polynomial< Coefficient >::Gen_Polynomial ( const DynList< Coefficient > & l )

inlineexplicit

Dense construction from DynList.

Same semantics as the initializer_list constructor.

Parameters

[in] l Coefficients in ascending exponent order.

Definition at line 409 of file tpl_polynomial.H.

References Aleph::Gen_Polynomial< Coefficient >::coeff_is_zero(), Aleph::Gen_Polynomial< Coefficient >::coeffs, Aleph::divide_and_conquer_partition_dp(), exp(), FunctionalMethods< Container, T >::for_each(), and l.

◆ Gen_Polynomial() [6/6]

template<typename Coefficient = double>

Aleph::Gen_Polynomial< Coefficient >::Gen_Polynomial ( const DynList< std::pair< size_t, Coefficient > > & term_list )

inlineexplicit

Sparse construction from a list of (exponent, coefficient) pairs.

Repeated exponents are accumulated, so the resulting polynomial is normalized even if the input list is not.

Parameters

[in] term_list Pairs of (exponent, coefficient).

Definition at line 427 of file tpl_polynomial.H.

References Aleph::Gen_Polynomial< Coefficient >::add_to_coeff(), Aleph::Gen_Polynomial< Coefficient >::coeff_is_zero(), and Aleph::divide_and_conquer_partition_dp().

Member Function Documentation

◆ _integer_exact_quot()

template<typename Coefficient = double>

static Gen_Polynomial Aleph::Gen_Polynomial< Coefficient >::_integer_exact_quot	(	const Gen_Polynomial< Coefficient > &	a,
		const Gen_Polynomial< Coefficient > &	b
	)

inlinestatic

Integer-safe exact quotient using pseudo-division.

Computes \(a / b\) for integer polynomials where b is known to divide a. Uses pseudo-division and normalizes the result.

Parameters

[in]	a	Dividend.
[in]	b	Divisor (must divide a exactly).

Returns: The primitive part of the quotient.

Exceptions

std::domain_error if b is zero or does not divide a exactly.

Definition at line 2111 of file tpl_polynomial.H.

References ah_domain_error_if, Aleph::Gen_Polynomial< Coefficient >::coeff_is_zero(), Aleph::Gen_Polynomial< Coefficient >::coeffs, Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Polynomial< Coefficient >::leading_coeff(), and r.

Referenced by TEST(), TEST(), TEST(), TEST(), and Aleph::Gen_Polynomial< Coefficient >::yun_sfd().

◆ add_scaled_shifted()

template<typename Coefficient = double>

void Aleph::Gen_Polynomial< Coefficient >::add_scaled_shifted	(	const Gen_Polynomial< Coefficient > &	src,
		const Coefficient &	scale,
		size_t	shift = `0`
	)

inlineprivate

Add scale times src shifted by shift to this polynomial.

Definition at line 257 of file tpl_polynomial.H.

References Aleph::Gen_Polynomial< Coefficient >::add_to_coeff(), Aleph::Gen_Polynomial< Coefficient >::coeff_is_zero(), Aleph::divide_and_conquer_partition_dp(), exp(), Aleph::Gen_Polynomial< Coefficient >::for_each_term(), Aleph::Gen_Polynomial< Coefficient >::is_zero(), and Aleph::Gen_Polynomial< Coefficient >::shift().

Referenced by Aleph::Gen_Polynomial< Coefficient >::interpolate().

◆ add_to_coeff()

template<typename Coefficient = double>

void Aleph::Gen_Polynomial< Coefficient >::add_to_coeff	(	size_t	exp,
		const Coefficient &	delta
	)

inlineprivate

Add a delta to one coefficient, erasing the term if it cancels.

Definition at line 241 of file tpl_polynomial.H.

References Aleph::Gen_Polynomial< Coefficient >::coeff_is_zero(), Aleph::Gen_Polynomial< Coefficient >::coeff_ptr(), Aleph::Gen_Polynomial< Coefficient >::coeffs, Aleph::divide_and_conquer_partition_dp(), and exp().

◆ bisect_root()

template<typename Coefficient = double>

Coefficient Aleph::Gen_Polynomial< Coefficient >::bisect_root	(	Coefficient	a,
		Coefficient	b,
		Coefficient	tol = `Coefficient(1e-12)`,
		size_t	max_iter = `200`
	)		const

inline

Find a root by bisection in \([a, b]\).

Requires \(p(a)\) and \(p(b)\) to have opposite signs.

Parameters

[in]	a	Lower bound (must satisfy \(p(a) \cdot p(b) < 0\)).
[in]	b	Upper bound.
[in]	tol	Convergence tolerance (default \(10^{-12}\)).
[in]	max_iter	Maximum iterations (default 200).

Returns: Approximate root.

Exceptions

std::domain_error if same sign at endpoints.

If a > b, the endpoints are swapped.

Definition at line 1661 of file tpl_polynomial.H.

References ah_domain_error_if, Aleph::and, Aleph::Gen_Polynomial< Coefficient >::coeff_is_zero(), Aleph::divide_and_conquer_partition_dp(), and Aleph::Gen_Polynomial< Coefficient >::eval().

Referenced by root_analysis(), TEST(), and TEST().

◆ cauchy_bound()

template<typename Coefficient = double>

Coefficient Aleph::Gen_Polynomial< Coefficient >::cauchy_bound ( ) const

inline

Cauchy upper bound on absolute value of roots.

For \(p(x) = a_d x^d + \ldots + a_0\), all roots \(|r|\) satisfy \(|r| \le 1 + \max_i |a_i / a_d|\).

Returns: Upper bound on \(\max |r_i|\).

Exceptions

std::domain_error if zero polynomial.

Definition at line 1457 of file tpl_polynomial.H.

References ah_domain_error_if, Aleph::Gen_Polynomial< Coefficient >::coeffs, Aleph::Gen_Polynomial< Coefficient >::degree(), Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Polynomial< Coefficient >::is_constant(), Aleph::Gen_Polynomial< Coefficient >::is_zero(), and Aleph::Gen_Polynomial< Coefficient >::leading_coeff().

Referenced by Aleph::Gen_Polynomial< Coefficient >::count_all_real_roots(), root_analysis(), TEST(), TEST(), TEST(), and TEST().

◆ coeff_at()

template<typename Coefficient = double>

Coefficient Aleph::Gen_Polynomial< Coefficient >::coeff_at ( size_t exp ) const

inlineprivate

Read coefficient at exponent (0 if absent).

Definition at line 220 of file tpl_polynomial.H.

References Aleph::Gen_Polynomial< Coefficient >::coeffs, Aleph::divide_and_conquer_partition_dp(), and exp().

Referenced by Aleph::Gen_Polynomial< Coefficient >::eval(), Aleph::Gen_Polynomial< Coefficient >::get_coeff(), Aleph::Gen_Polynomial< Coefficient >::horner_eval(), and Aleph::Gen_Polynomial< Coefficient >::operator[]().

◆ coeff_is_zero()

template<typename Coefficient = double>

static bool Aleph::Gen_Polynomial< Coefficient >::coeff_is_zero ( const Coefficient & c )

inlinestaticprivatenoexcept

Test whether a coefficient is (approximately) zero.

For floating-point types, uses std::abs(c) <= epsilon(). For exact types, uses c == Coefficient{}.

Definition at line 195 of file tpl_polynomial.H.

References Aleph::divide_and_conquer_partition_dp(), and Aleph::Gen_Polynomial< Coefficient >::epsilon().

◆ coeff_ptr() [1/2]

template<typename Coefficient = double>

const Coefficient * Aleph::Gen_Polynomial< Coefficient >::coeff_ptr ( size_t exp ) const

inlineprivatenoexcept

Pointer to stored coefficient, or null if absent.

Definition at line 234 of file tpl_polynomial.H.

References Aleph::Gen_Polynomial< Coefficient >::coeffs, and exp().

◆ coeff_ptr() [2/2]

template<typename Coefficient = double>

Coefficient * Aleph::Gen_Polynomial< Coefficient >::coeff_ptr ( size_t exp )

inlineprivatenoexcept

Pointer to stored coefficient, or null if absent.

Definition at line 227 of file tpl_polynomial.H.

References Aleph::Gen_Polynomial< Coefficient >::coeffs, and exp().

Referenced by Aleph::Gen_Polynomial< Coefficient >::add_to_coeff(), and Aleph::Gen_Polynomial< Coefficient >::set_coeff().

◆ coefficients()

template<typename Coefficient = double>

DynList< Coefficient > Aleph::Gen_Polynomial< Coefficient >::coefficients ( ) const

inline

All non-zero coefficients in ascending exponent order.

Definition at line 1845 of file tpl_polynomial.H.

References Aleph::Gen_Polynomial< Coefficient >::coeffs.

◆ compose()

template<typename Coefficient = double>

Gen_Polynomial Aleph::Gen_Polynomial< Coefficient >::compose ( const Gen_Polynomial< Coefficient > & q ) const

inline

Composition \(p(q(x))\).

Evaluates this polynomial at q using a sparse-aware Horner scheme over non-zero coefficients, so large exponent gaps do not force repeated multiplication by q for zero coefficients.

Definition at line 1082 of file tpl_polynomial.H.

References Aleph::Gen_Polynomial< Coefficient >::Gen_Polynomial(), Aleph::Gen_Polynomial< Coefficient >::add_to_coeff(), Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Polynomial< Coefficient >::eval(), exp(), Aleph::Gen_Polynomial< Coefficient >::for_each_term_desc(), Aleph::Gen_Polynomial< Coefficient >::is_constant(), Aleph::Gen_Polynomial< Coefficient >::is_zero(), and Aleph::Gen_Polynomial< Coefficient >::pow().

Referenced by Aleph::Gen_Polynomial< Coefficient >::shift(), sparse_polynomials(), TEST(), TEST(), TEST(), and TEST().

◆ content()

template<typename Coefficient = double>

Coefficient Aleph::Gen_Polynomial< Coefficient >::content ( ) const

inline

Content: GCD of all coefficients.

For an integer polynomial \(p(x) = a_d x^d + \ldots + a_0\), the content is \(\gcd(a_d, \ldots, a_0)\).

For the zero polynomial, returns zero. For a non-zero polynomial, the sign follows the leading coefficient.

Note: Only available for integral coefficient types.

Returns: The GCD of all coefficients.

Definition at line 1958 of file tpl_polynomial.H.

References Aleph::and, Aleph::Gen_Polynomial< Coefficient >::coeffs, Aleph::divide_and_conquer_partition_dp(), and Aleph::Gen_Polynomial< Coefficient >::leading_coeff().

Referenced by Aleph::Gen_Polynomial< Coefficient >::factorize(), Aleph::Gen_Polynomial< Coefficient >::primitive_part(), TEST(), TEST(), TEST(), and TEST().

◆ count_all_real_roots()

template<typename Coefficient = double>

size_t Aleph::Gen_Polynomial< Coefficient >::count_all_real_roots ( ) const

inline

Total number of distinct real roots.

Counts all distinct real roots using Sturm's theorem with the Cauchy bound.

Definition at line 1640 of file tpl_polynomial.H.

References Aleph::Gen_Polynomial< Coefficient >::cauchy_bound(), Aleph::Gen_Polynomial< Coefficient >::count_real_roots(), Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Polynomial< Coefficient >::is_constant(), and Aleph::Gen_Polynomial< Coefficient >::is_zero().

Referenced by root_analysis(), and TEST().

◆ count_real_roots()

template<typename Coefficient = double>

size_t Aleph::Gen_Polynomial< Coefficient >::count_real_roots	(	const Coefficient &	a,
		const Coefficient &	b
	)		const

inline

Count distinct real roots in \([a, b]\) via Sturm's theorem.

Parameters

[in]	a	Lower bound of interval.
[in]	b	Upper bound of interval.

Returns: Number of distinct real roots in \([a, b]\).

Note: Only meaningful for floating-point coefficient types. If a > b, the endpoints are swapped. The zero polynomial is treated as having 0 countable distinct roots.; Complexity: \(O(d^2)\) to build the Sturm chain, plus \(O(d^2)\) for evaluating it at both endpoints.

Definition at line 1615 of file tpl_polynomial.H.

References Aleph::Gen_Polynomial< Coefficient >::coeff_is_zero(), Aleph::count(), Aleph::Gen_Polynomial< Coefficient >::count_real_roots(), Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Polynomial< Coefficient >::is_zero(), Aleph::Gen_Polynomial< Coefficient >::sturm_chain(), and Aleph::Gen_Polynomial< Coefficient >::sturm_sign_changes().

Referenced by Aleph::Gen_Polynomial< Coefficient >::count_all_real_roots(), Aleph::Gen_Polynomial< Coefficient >::count_real_roots(), root_analysis(), TEST(), and TEST().

◆ definite_integral()

template<typename Coefficient = double>

Coefficient Aleph::Gen_Polynomial< Coefficient >::definite_integral	(	const Coefficient &	a,
		const Coefficient &	b
	)		const

inline

Definite integral \(\int_a^b p(x)\,dx\).

Computes the integral term by term without materializing the full antiderivative polynomial.

Parameters

[in]	a	Lower bound.
[in]	b	Upper bound.

Returns: \(\int_a^b p(x)\,dx\).

Definition at line 1052 of file tpl_polynomial.H.

References Aleph::Gen_Polynomial< Coefficient >::coeff_is_zero(), Aleph::Gen_Polynomial< Coefficient >::coeffs, Aleph::divide_and_conquer_partition_dp(), and Aleph::polynomial_detail::power().

◆ degree()

template<typename Coefficient = double>

size_t Aleph::Gen_Polynomial< Coefficient >::degree ( ) const

inlinenoexcept

Degree of the polynomial.

Returns 0 for the zero polynomial. Use is_zero() to distinguish the zero polynomial from a non-zero constant.

Definition at line 552 of file tpl_polynomial.H.

References Aleph::Gen_Polynomial< Coefficient >::coeffs.

◆ derivative()

template<typename Coefficient = double>

Gen_Polynomial Aleph::Gen_Polynomial< Coefficient >::derivative ( ) const

inline

Formal derivative \(p'(x)\).

\(\frac{d}{dx}\bigl[\sum c_i x^{e_i}\bigr] = \sum e_i \cdot c_i \cdot x^{e_i - 1}\).

Definition at line 984 of file tpl_polynomial.H.

References Aleph::Gen_Polynomial< Coefficient >::coeff_is_zero(), Aleph::Gen_Polynomial< Coefficient >::coeffs, and Aleph::divide_and_conquer_partition_dp().

Referenced by calculus_example(), Aleph::Gen_Polynomial< Coefficient >::hensel_lift(), Aleph::Gen_Polynomial< Coefficient >::newton_root(), Aleph::Gen_Polynomial< Coefficient >::nth_derivative(), sparse_polynomials(), Aleph::Gen_Polynomial< Coefficient >::square_free(), Aleph::Gen_Polynomial< Coefficient >::sturm_chain(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), and Aleph::Gen_Polynomial< Coefficient >::yun_sfd().

◆ divide_by_monic_linear_mod()

template<typename Coefficient = double>

static Gen_Polynomial Aleph::Gen_Polynomial< Coefficient >::divide_by_monic_linear_mod	(	const Gen_Polynomial< Coefficient > &	f,
		Coefficient	root,
		Coefficient	mod
	)

inlinestatic

Definition at line 2167 of file tpl_polynomial.H.

References ah_domain_error_if, Aleph::Gen_Polynomial< Coefficient >::degree(), Aleph::divide_and_conquer_partition_dp(), exp(), Aleph::next(), root(), and Aleph::Gen_Polynomial< Coefficient >::set_coeff().

Referenced by Aleph::Gen_Polynomial< Coefficient >::factor_mod_p().

◆ divide_scalar_inplace()

template<typename Coefficient = double>

void Aleph::Gen_Polynomial< Coefficient >::divide_scalar_inplace ( const Coefficient & s )

inlineprivate

Divide every coefficient in place by a scalar.

Definition at line 299 of file tpl_polynomial.H.

References ah_domain_error_if, Aleph::DynList< T >::append(), Aleph::Gen_Polynomial< Coefficient >::coeff_is_zero(), Aleph::Gen_Polynomial< Coefficient >::coeffs, Aleph::divide_and_conquer_partition_dp(), exp(), and FunctionalMethods< Container, T >::for_each().

Referenced by Aleph::Gen_Polynomial< Coefficient >::operator/=().

◆ divmod()

template<typename Coefficient = double>

std::pair< Gen_Polynomial, Gen_Polynomial > Aleph::Gen_Polynomial< Coefficient >::divmod ( const Gen_Polynomial< Coefficient > & d ) const

inline

Polynomial long division: returns (quotient, remainder).

Computes \(q\) and \(r\) such that \(\text{this} = q \cdot d + r\) with \(\deg(r) < \deg(d)\) or \(r = 0\).

Parameters

[in] d Divisor (must not be zero).

Returns: Pair (quotient, remainder).

Exceptions

std::domain_error if d is zero.

Definition at line 917 of file tpl_polynomial.H.

References Aleph::Gen_Polynomial< Coefficient >::Gen_Polynomial(), Aleph::Gen_Polynomial< Coefficient >::add_to_coeff(), ah_domain_error_if, Aleph::Gen_Polynomial< Coefficient >::coeff_is_zero(), Aleph::Gen_Polynomial< Coefficient >::degree(), Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Polynomial< Coefficient >::is_zero(), Aleph::Gen_Polynomial< Coefficient >::leading_coeff(), r, and Aleph::Gen_Polynomial< Coefficient >::shift().

Referenced by basic_arithmetic(), Aleph::Gen_Polynomial< Coefficient >::operator%(), Aleph::Gen_Polynomial< Coefficient >::operator%=(), Aleph::Gen_Polynomial< Coefficient >::operator/(), Aleph::Gen_Polynomial< Coefficient >::operator/=(), TEST(), TEST(), TEST(), TEST(), TEST(), and Aleph::Gen_Polynomial< Coefficient >::xgcd().

◆ epsilon()

template<typename Coefficient = double>

static constexpr Coefficient Aleph::Gen_Polynomial< Coefficient >::epsilon ( )

inlinestaticconstexprprivatenoexcept

Tolerance threshold for floating-point zero detection.

Returns \(128 \cdot \varepsilon\) for floating-point types and the additive identity for all others.

Definition at line 182 of file tpl_polynomial.H.

References Aleph::divide_and_conquer_partition_dp().

Referenced by Aleph::Gen_Polynomial< Coefficient >::coeff_is_zero(), and Aleph::Gen_Polynomial< Coefficient >::sign_variations().

◆ eval()

template<typename Coefficient = double>

Coefficient Aleph::Gen_Polynomial< Coefficient >::eval ( const Coefficient & x ) const

inline

Evaluate \(p(x)\) with adaptive strategy.

Uses direct term evaluation for ultra-sparse polynomials and the gap-aware Horner path otherwise.

Parameters

[in] x Evaluation point.

Returns: \(p(x)\).

Definition at line 682 of file tpl_polynomial.H.

References Aleph::Gen_Polynomial< Coefficient >::coeff_at(), Aleph::Gen_Polynomial< Coefficient >::coeffs, Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Polynomial< Coefficient >::horner_eval(), Aleph::Gen_Polynomial< Coefficient >::num_terms(), and Aleph::Gen_Polynomial< Coefficient >::sparse_eval().

Referenced by Aleph::Gen_Polynomial< Coefficient >::bisect_root(), Aleph::Gen_Polynomial< Coefficient >::compose(), Aleph::Gen_Polynomial< Coefficient >::multi_eval(), Aleph::Gen_Polynomial< Coefficient >::newton_root(), Aleph::Gen_Polynomial< Coefficient >::operator()(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), and TEST().

◆ eval_mod_u64()

template<typename Coefficient = double>

static uint64_t Aleph::Gen_Polynomial< Coefficient >::eval_mod_u64	(	const Gen_Polynomial< Coefficient > &	f,
		uint64_t	x,
		uint64_t	mod
	)

inlinestatic

Definition at line 2150 of file tpl_polynomial.H.

References Aleph::divide_and_conquer_partition_dp(), exp(), Aleph::Gen_Polynomial< Coefficient >::for_each_term(), Aleph::mod_exp(), Aleph::mod_mul(), and Aleph::polynomial_detail::normalize_mod_u64().

Referenced by Aleph::Gen_Polynomial< Coefficient >::factor_mod_p(), and Aleph::Gen_Polynomial< Coefficient >::hensel_lift().

◆ exponents()

template<typename Coefficient = double>

DynList< size_t > Aleph::Gen_Polynomial< Coefficient >::exponents ( ) const

inline

All exponents with non-zero coefficients (sorted ascending).

Definition at line 1839 of file tpl_polynomial.H.

References Aleph::Gen_Polynomial< Coefficient >::coeffs, and GenericItems< Container, T >::keys().

Referenced by TEST().

◆ factor_mod_p()

template<typename Coefficient = double>

static DynList< Gen_Polynomial > Aleph::Gen_Polynomial< Coefficient >::factor_mod_p	(	const Gen_Polynomial< Coefficient > &	f,
		Coefficient	p
	)

inlinestatic

Factorization over integers mod p (trial method).

Finds all linear factors over \(\mathbb{Z}/p\mathbb{Z}\) by exhaustive root search and repeated extraction. Any unfactored residual polynomial is appended as the final element.

Parameters

[in]	f	Polynomial to factor.
[in]	p	The prime modulus.

Returns: A list of monic linear factors (with multiplicity), plus a final residual factor if non-constant.

Exceptions

std::domain_error if p <= 1.

Note: Only available for integral coefficient types.; This is still a root-search method, not Berlekamp or Cantor-Zassenhaus; non-linear irreducible factors remain grouped.

Definition at line 2523 of file tpl_polynomial.H.

References Aleph::polynomial_detail::abs_to_u64(), ah_domain_error_if, Aleph::and, Aleph::DynList< T >::append(), Aleph::Gen_Polynomial< Coefficient >::degree(), Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Polynomial< Coefficient >::divide_by_monic_linear_mod(), Aleph::Gen_Polynomial< Coefficient >::eval_mod_u64(), Aleph::Gen_Polynomial< Coefficient >::is_constant(), Aleph::Gen_Polynomial< Coefficient >::is_zero(), Aleph::polynomial_detail::normalize_mod_u64(), r, Aleph::Gen_Polynomial< Coefficient >::reduce_coeffs_mod(), and Aleph::Gen_Polynomial< Coefficient >::set_coeff().

Referenced by Aleph::Gen_Polynomial< Coefficient >::factorize(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), and TEST().

◆ factorize()

template<typename Coefficient = double>

DynList< SfdTerm > Aleph::Gen_Polynomial< Coefficient >::factorize ( ) const

inline

Main factorization over integers.

Combines square-free decomposition (SFD), exact extraction of rational linear factors, and modular root search / Hensel lifting heuristics for any remaining square-free blocks.

Algorithm outline:

Compute the primitive part (remove common factors).
Apply Yun's SFD to group factors by multiplicity.
For each square-free group, extract exact primitive linear, quadratic, and cubic factors over \(\mathbb{Z}\).
For any residual factor, use modular root search plus Hensel lifting of simple linear roots to discover additional exact divisors.

Returns: A list of SfdTerm where each factor is irreducible (or as close as possible with this algorithm).

Note: Only available for integral coefficient types.; If the polynomial has non-unit content, the returned list includes that constant factor with multiplicity 1 so the original polynomial reconstructs exactly.; This remains a lightweight implementation. It is strong on exact linear, quadratic, and cubic factors and conservative on higher-degree residuals.; Every factor returned here is validated by exact division, but a remaining higher-degree block should be interpreted as "not split further by this algorithm", not as a proof of irreducibility over \(\mathbb{Z}\).; Complexity: depends on SFD and modular factorization.

Definition at line 2744 of file tpl_polynomial.H.

Referenced by algebraic_transformations(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), and TEST().

◆ for_each_term()

template<typename Coefficient = double>

template<class Op >

void Aleph::Gen_Polynomial< Coefficient >::for_each_term ( Op && op ) const

inline

Iterate over non-zero terms in ascending exponent order.

The callable op receives (size_t exponent, const Coefficient &).

Definition at line 1817 of file tpl_polynomial.H.

References Aleph::Gen_Polynomial< Coefficient >::coeffs.

Referenced by Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::_embed_univariate(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::_factorize_as_univariate_in_var(), Aleph::Gen_Polynomial< Coefficient >::add_scaled_shifted(), Aleph::Gen_Polynomial< Coefficient >::eval_mod_u64(), Aleph::Gen_Polynomial< Coefficient >::hensel_lift(), Aleph::Gen_Polynomial< Coefficient >::reduce_coeffs_mod(), TEST(), and transfer_function().

◆ for_each_term_desc()

template<typename Coefficient = double>

template<class Op >

void Aleph::Gen_Polynomial< Coefficient >::for_each_term_desc ( Op && op ) const

inlineprivate

Iterate over non-zero terms in descending exponent order.

Definition at line 326 of file tpl_polynomial.H.

References Aleph::Gen_Polynomial< Coefficient >::coeffs, and Aleph::divide_and_conquer_partition_dp().

Referenced by Aleph::Gen_Polynomial< Coefficient >::compose(), Aleph::Gen_Polynomial< Coefficient >::horner_eval(), and Aleph::Gen_Polynomial< Coefficient >::to_str().

◆ from_roots()

template<typename Coefficient = double>

static Gen_Polynomial Aleph::Gen_Polynomial< Coefficient >::from_roots ( const DynList< Coefficient > & roots )

inlinestatic

Build polynomial from its roots: \(\prod (x - r_i)\).

Parameters

[in] roots List of roots.

Returns: The monic polynomial whose roots are exactly roots (with multiplicity).

Note: Uses a specialized linear-factor multiplication path to avoid the overhead of generic polynomial products.

Definition at line 469 of file tpl_polynomial.H.

References Aleph::divide_and_conquer_partition_dp(), FunctionalMethods< Container, T >::for_each(), Aleph::Gen_Polynomial< Coefficient >::multiply_by_monic_linear(), and r.

Referenced by root_analysis(), roots_and_interpolation(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), and TEST().

◆ gcd()

template<typename Coefficient = double>

static Gen_Polynomial Aleph::Gen_Polynomial< Coefficient >::gcd	(	Gen_Polynomial< Coefficient >	a,
		Gen_Polynomial< Coefficient >	b
	)

inlinestatic

Greatest common divisor (Euclidean algorithm).

Returns a monic GCD (leading coefficient 1) for field-like coefficient types. For integer coefficients, the result is normalized by dividing by its leading coefficient.

Note: Only meaningful for coefficient types that form a field (rationals, floating-point).

Definition at line 1154 of file tpl_polynomial.H.

References Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Polynomial< Coefficient >::is_zero(), Aleph::Gen_Polynomial< Coefficient >::leading_coeff(), and r.

Referenced by Aleph::Gen_Polynomial< Coefficient >::lcm(), Aleph::Gen_Polynomial< Coefficient >::square_free(), TEST(), and TEST().

◆ get_coeff()

template<typename Coefficient = double>

Coefficient Aleph::Gen_Polynomial< Coefficient >::get_coeff ( size_t exp ) const

inlinenoexcept

Coefficient accessor (read-only at exponent).

Returns the coefficient at exp, or Coefficient{} (zero) if absent. This is equivalent to operator[].

Definition at line 1924 of file tpl_polynomial.H.

References Aleph::Gen_Polynomial< Coefficient >::coeff_at(), and exp().

Referenced by Aleph::Gen_Polynomial< Coefficient >::factorize(), Aleph::Gen_Polynomial< Coefficient >::hensel_lift(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::homomorphic_eval(), TEST(), TEST(), TEST(), TEST(), TEST(), and TEST().

◆ has_term()

template<typename Coefficient = double>

bool Aleph::Gen_Polynomial< Coefficient >::has_term ( size_t exp ) const

inlinenoexcept

True if there is a non-zero coefficient at exp.

Definition at line 604 of file tpl_polynomial.H.

References Aleph::Gen_Polynomial< Coefficient >::coeffs, and exp().

◆ hensel_lift()

template<typename Coefficient = double>

static DynList< Gen_Polynomial > Aleph::Gen_Polynomial< Coefficient >::hensel_lift	(	const Gen_Polynomial< Coefficient > &	f,
		DynList< Gen_Polynomial< Coefficient > >	factors,
		Coefficient	p,
		size_t	levels
	)

inlinestatic

Hensel lifting of modular factors.

Given modular factors of \(f \pmod p \), lifts any monic linear factor corresponding to a simple root to modulus \(p^{2^\text{levels}}\) using repeated Hensel root lifting. Factors that are not monic linear simple-root factors are carried through reduced modulo the target modulus.

Parameters

[in]	f	Original polynomial.
[in]	factors	Factors mod `p` (must multiply to `f` mod `p`).
[in]	p	The prime modulus.
[in]	levels	Number of lifting iterations (quadratic).

Returns: Factors lifted to \(\mathbb{Z}/p^{2^\text{levels}}\mathbb{Z}\).

Exceptions

std::domain_error if p <= 1 or levels > 30.

Note: Only available for integral coefficient types.; Singular roots are not lifted; such factors are returned only normalized modulo the target modulus.

Warning: levels > 30 is rejected to prevent overflow in (1 << levels).

Definition at line 2616 of file tpl_polynomial.H.

References Aleph::polynomial_detail::abs_to_u64(), ah_domain_error_if, Aleph::and, Aleph::DynList< T >::append(), Aleph::Gen_Polynomial< Coefficient >::degree(), Aleph::Gen_Polynomial< Coefficient >::derivative(), Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Polynomial< Coefficient >::eval_mod_u64(), exp(), Aleph::Gen_Polynomial< Coefficient >::for_each_term(), Aleph::Gen_Polynomial< Coefficient >::get_coeff(), Aleph::mod_inv(), Aleph::mod_mul(), Aleph::polynomial_detail::normalize_mod_u64(), root(), and Aleph::Gen_Polynomial< Coefficient >::set_coeff().

Referenced by Aleph::Gen_Polynomial< Coefficient >::factorize(), TEST(), TEST(), TEST(), TEST(), TEST(), and TEST().

◆ horner_eval()

template<typename Coefficient = double>

Coefficient Aleph::Gen_Polynomial< Coefficient >::horner_eval ( const Coefficient & x ) const

inline

Evaluate \(p(x)\) using gap-aware Horner's method.

Consecutive blocks of missing coefficients are collapsed into powers of x, so sparse high-degree polynomials do not pay a lookup per zero coefficient.

Parameters

[in] x Evaluation point.

Returns: \(p(x)\).

Definition at line 622 of file tpl_polynomial.H.

References Aleph::Gen_Polynomial< Coefficient >::coeff_at(), Aleph::Gen_Polynomial< Coefficient >::coeffs, Aleph::divide_and_conquer_partition_dp(), exp(), Aleph::Gen_Polynomial< Coefficient >::for_each_term_desc(), and Aleph::polynomial_detail::power().

Referenced by Aleph::Gen_Polynomial< Coefficient >::eval(), and TEST().

◆ integer_gcd()

template<typename Coefficient = double>

static Gen_Polynomial Aleph::Gen_Polynomial< Coefficient >::integer_gcd	(	Gen_Polynomial< Coefficient >	a,
		Gen_Polynomial< Coefficient >	b
	)

inlinestatic

Polynomial GCD over integers (Euclidean algorithm with primitive parts).

Computes \(\gcd(a, b)\) for integer polynomials using the Euclidean algorithm, normalizing by primitive parts at each step.

Parameters

[in]	a	First polynomial.
[in]	b	Second polynomial.

Returns: The GCD polynomial (monic up to units).

Note: Only available for integral coefficient types.; Complexity: \(O(d^2)\) polynomial divisions.

Definition at line 2029 of file tpl_polynomial.H.

References Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Polynomial< Coefficient >::primitive_part(), and Aleph::Gen_Polynomial< Coefficient >::pseudo_divmod().

Referenced by TEST(), TEST(), TEST(), TEST(), and Aleph::Gen_Polynomial< Coefficient >::yun_sfd().

◆ integral()

template<typename Coefficient = double>

Gen_Polynomial Aleph::Gen_Polynomial< Coefficient >::integral ( const Coefficient & C = Coefficient{} ) const

inline

Formal indefinite integral with constant of integration.

\(\int \sum c_i x^{e_i}\,dx = C + \sum \frac{c_i}{e_i + 1} x^{e_i + 1}\)

Parameters

[in] C Constant of integration (default 0).

Note: For integer coefficient types, division truncates. Use a rational type for exact results.

Definition at line 1028 of file tpl_polynomial.H.

Referenced by calculus_example(), TEST(), TEST(), and TEST().

◆ interpolate()

template<typename Coefficient = double>

static Gen_Polynomial Aleph::Gen_Polynomial< Coefficient >::interpolate ( const DynList< std::pair< Coefficient, Coefficient > > & points )

inlinestatic

Polynomial interpolation through a set of points.

Given \(n+1\) points \((x_i, y_i)\), returns the unique polynomial of degree at most \(n\) passing through all of them.

Parameters

[in] points List of (x, y) pairs. The x-values must be distinct.

Returns: The interpolating polynomial.

Exceptions

std::domain_error if fewer than 1 point or duplicate x-values.

Note: Implemented via Newton divided differences plus incremental linear-factor expansion, avoiding the large temporary basis polynomials of the naive Lagrange form.

Definition at line 493 of file tpl_polynomial.H.

References Aleph::Gen_Polynomial< Coefficient >::add_scaled_shifted(), ah_domain_error_if, Aleph::Gen_Polynomial< Coefficient >::coeff_is_zero(), Aleph::divide_and_conquer_partition_dp(), and Aleph::Array< T >::putn().

Referenced by roots_and_interpolation(), TEST(), TEST(), TEST(), and TEST().

◆ is_constant()

template<typename Coefficient = double>

bool Aleph::Gen_Polynomial< Coefficient >::is_constant ( ) const

inlinenoexcept

True if constant or zero.

Definition at line 566 of file tpl_polynomial.H.

References Aleph::and, Aleph::Gen_Polynomial< Coefficient >::coeffs, and Aleph::divide_and_conquer_partition_dp().

Referenced by Aleph::Gen_Polynomial< Coefficient >::cauchy_bound(), Aleph::Gen_Polynomial< Coefficient >::compose(), Aleph::Gen_Polynomial< Coefficient >::count_all_real_roots(), Aleph::Gen_Polynomial< Coefficient >::factor_mod_p(), Aleph::Gen_Polynomial< Coefficient >::factorize(), Aleph::Gen_Polynomial< Coefficient >::square_free(), Aleph::Gen_Polynomial< Coefficient >::sturm_chain(), TEST(), and Aleph::Gen_Polynomial< Coefficient >::yun_sfd().

◆ is_monic()

template<typename Coefficient = double>

bool Aleph::Gen_Polynomial< Coefficient >::is_monic ( ) const

inlinenoexcept

True if leading coefficient equals 1.

Definition at line 578 of file tpl_polynomial.H.

References Aleph::and, Aleph::Gen_Polynomial< Coefficient >::coeff_is_zero(), Aleph::Gen_Polynomial< Coefficient >::coeffs, and Aleph::divide_and_conquer_partition_dp().

◆ is_monomial()

template<typename Coefficient = double>

bool Aleph::Gen_Polynomial< Coefficient >::is_monomial ( ) const

inlinenoexcept

True if exactly one non-zero term.

Definition at line 572 of file tpl_polynomial.H.

References Aleph::Gen_Polynomial< Coefficient >::coeffs.

Referenced by TEST().

◆ is_zero()

template<typename Coefficient = double>

bool Aleph::Gen_Polynomial< Coefficient >::is_zero ( ) const

inlinenoexcept

True if this is the zero polynomial.

Definition at line 542 of file tpl_polynomial.H.

References Aleph::Gen_Polynomial< Coefficient >::coeffs.

◆ lcm()

template<typename Coefficient = double>

static Gen_Polynomial Aleph::Gen_Polynomial< Coefficient >::lcm	(	const Gen_Polynomial< Coefficient > &	a,
		const Gen_Polynomial< Coefficient > &	b
	)

inlinestatic

Least common multiple.

\(\text{lcm}(a, b) = \frac{a \cdot b}{\gcd(a, b)}\).

Parameters

[in]	a	First polynomial.
[in]	b	Second polynomial.

Returns: The LCM, or the zero polynomial if either input is zero.

Definition at line 1221 of file tpl_polynomial.H.

References Aleph::Gen_Polynomial< Coefficient >::Gen_Polynomial(), Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Polynomial< Coefficient >::gcd(), and Aleph::Gen_Polynomial< Coefficient >::is_zero().

Referenced by TEST(), and TEST().

◆ leading_coeff()

template<typename Coefficient = double>

Coefficient Aleph::Gen_Polynomial< Coefficient >::leading_coeff ( ) const

inlinenoexcept

Leading coefficient (of the highest-degree term).

Returns: Coefficient{} if zero polynomial.

Definition at line 596 of file tpl_polynomial.H.

References Aleph::Gen_Polynomial< Coefficient >::coeffs, and Aleph::divide_and_conquer_partition_dp().

◆ mignotte_bound()

template<typename Coefficient = double>

double Aleph::Gen_Polynomial< Coefficient >::mignotte_bound ( ) const

inline

Mignotte bound on integer roots.

For an integer polynomial of degree \(d\) with coefficients \(a_0, \ldots, a_d\), any rational root \(p/q\) with gcd(p,q)=1 satisfies:

\[ |p| \le \sqrt{d+1} \cdot 2^d \cdot \max_i |a_i| \]

Returns: Upper bound on absolute value of integer roots.

Definition at line 2569 of file tpl_polynomial.H.

References Aleph::Gen_Polynomial< Coefficient >::coeffs, Aleph::Gen_Polynomial< Coefficient >::degree(), Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Polynomial< Coefficient >::is_zero(), and Aleph::polynomial_detail::power().

Referenced by TEST(), and TEST().

◆ multi_eval()

template<typename Coefficient = double>

DynList< Coefficient > Aleph::Gen_Polynomial< Coefficient >::multi_eval ( const DynList< Coefficient > & points ) const

inline

Evaluate at multiple points.

Parameters

[in] points List of evaluation points.

Returns: List of \(p(x_i)\) in corresponding order.

Note: Complexity: \(O(m \cdot T_{\text{eval}})\) where \(m\) is the number of points and \(T_{\text{eval}}\) is the per-point evaluation cost (see eval).

Definition at line 711 of file tpl_polynomial.H.

References Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Polynomial< Coefficient >::eval(), and FunctionalMethods< Container, T >::for_each().

◆ multiply_by_monic_linear()

template<typename Coefficient = double>

Gen_Polynomial Aleph::Gen_Polynomial< Coefficient >::multiply_by_monic_linear ( const Coefficient & c ) const

inlineprivate

Specialized multiplication by a monic linear factor \(x + c\).

Definition at line 343 of file tpl_polynomial.H.

References Aleph::Gen_Polynomial< Coefficient >::Gen_Polynomial(), Aleph::Gen_Polynomial< Coefficient >::add_to_coeff(), Aleph::Gen_Polynomial< Coefficient >::coeffs, and Aleph::Gen_Polynomial< Coefficient >::is_zero().

Referenced by Aleph::Gen_Polynomial< Coefficient >::from_roots().

◆ negate_arg()

template<typename Coefficient = double>

Gen_Polynomial Aleph::Gen_Polynomial< Coefficient >::negate_arg ( ) const

inline

Argument negation: \(p(-x)\).

Negates coefficients of odd-degree terms.

Definition at line 1321 of file tpl_polynomial.H.

References Aleph::Gen_Polynomial< Coefficient >::coeffs.

Referenced by root_analysis(), TEST(), and TEST().

◆ newton_root()

template<typename Coefficient = double>

Coefficient Aleph::Gen_Polynomial< Coefficient >::newton_root	(	Coefficient	x0,
		Coefficient	tol = `Coefficient(1e-12)`,
		size_t	max_iter = `100`
	)		const

inline

Find a root by Newton-Raphson iteration.

Parameters

[in]	x0	Initial guess.
[in]	tol	Convergence tolerance (default \(10^{-12}\)).
[in]	max_iter	Maximum iterations (default 100).

Returns: Approximate root.

Exceptions

std::domain_error if derivative vanishes during iteration.

Note: Only available for floating-point coefficient types.

Definition at line 1710 of file tpl_polynomial.H.

References ah_domain_error_if, Aleph::Gen_Polynomial< Coefficient >::coeff_is_zero(), Aleph::Gen_Polynomial< Coefficient >::derivative(), Aleph::divide_and_conquer_partition_dp(), and Aleph::Gen_Polynomial< Coefficient >::eval().

Referenced by root_analysis(), TEST(), TEST(), and TEST().

◆ nth_derivative()

template<typename Coefficient = double>

Gen_Polynomial Aleph::Gen_Polynomial< Coefficient >::nth_derivative ( size_t n ) const

inline

\(n\)-th derivative \(p^{(n)}(x)\).

Applies the derivative operator n times. Returns the zero polynomial if \(n > \deg(p)\).

Parameters

[in] n Differentiation order.

Returns: The n-th derivative.

Note: Complexity: \(O(n \cdot k)\) where \(k\) is the number of terms.

Definition at line 1010 of file tpl_polynomial.H.

References Aleph::and, Aleph::Gen_Polynomial< Coefficient >::derivative(), Aleph::divide_and_conquer_partition_dp(), and Aleph::Gen_Polynomial< Coefficient >::is_zero().

Referenced by calculus_example(), and TEST().

◆ num_terms()

template<typename Coefficient = double>

size_t Aleph::Gen_Polynomial< Coefficient >::num_terms ( ) const

inlinenoexcept

Number of non-zero terms.

Definition at line 560 of file tpl_polynomial.H.

References Aleph::Gen_Polynomial< Coefficient >::coeffs.

Referenced by Aleph::Gen_Polynomial< Coefficient >::eval(), Aleph::Gen_Polynomial< Coefficient >::operator*(), sparse_polynomials(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), and TEST().

◆ one()

template<typename Coefficient = double>

static Gen_Polynomial Aleph::Gen_Polynomial< Coefficient >::one ( )

inlinestatic

The constant polynomial 1.

Definition at line 447 of file tpl_polynomial.H.

References Aleph::Gen_Polynomial< Coefficient >::Gen_Polynomial(), and Aleph::divide_and_conquer_partition_dp().

Referenced by TEST().

◆ operator!=()

template<typename Coefficient = double>

bool Aleph::Gen_Polynomial< Coefficient >::operator!= ( const Gen_Polynomial< Coefficient > & q ) const

inlinenoexcept

Inequality comparison.

Definition at line 1803 of file tpl_polynomial.H.

References Aleph::divide_and_conquer_partition_dp().

◆ operator%()

template<typename Coefficient = double>

Gen_Polynomial Aleph::Gen_Polynomial< Coefficient >::operator% ( const Gen_Polynomial< Coefficient > & d ) const

inline

Polynomial remainder.

Definition at line 956 of file tpl_polynomial.H.

References Aleph::Gen_Polynomial< Coefficient >::divmod().

◆ operator%=()

template<typename Coefficient = double>

Gen_Polynomial & Aleph::Gen_Polynomial< Coefficient >::operator%= ( const Gen_Polynomial< Coefficient > & d )

inline

In-place polynomial remainder.

Definition at line 969 of file tpl_polynomial.H.

References Aleph::Gen_Polynomial< Coefficient >::divmod().

◆ operator()()

template<typename Coefficient = double>

Coefficient Aleph::Gen_Polynomial< Coefficient >::operator() ( const Coefficient & x ) const

inline

Syntactic sugar: p(x) calls eval.

Definition at line 697 of file tpl_polynomial.H.

References Aleph::Gen_Polynomial< Coefficient >::eval().

◆ operator*() [1/2]

template<typename Coefficient = double>

Gen_Polynomial Aleph::Gen_Polynomial< Coefficient >::operator* ( const Coefficient & s ) const

inline

Multiply by a scalar.

Definition at line 857 of file tpl_polynomial.H.

References Aleph::Gen_Polynomial< Coefficient >::Gen_Polynomial(), Aleph::Gen_Polynomial< Coefficient >::coeff_is_zero(), Aleph::Gen_Polynomial< Coefficient >::coeffs, and Aleph::divide_and_conquer_partition_dp().

◆ operator*() [2/2]

template<typename Coefficient = double>

Gen_Polynomial Aleph::Gen_Polynomial< Coefficient >::operator* ( const Gen_Polynomial< Coefficient > & q ) const

inline

Polynomial multiplication.

Note: Complexity: \(O(k_1 \cdot k_2 \cdot \log(k_1 k_2))\) where \(k_1, k_2\) are the numbers of terms.

Definition at line 822 of file tpl_polynomial.H.

References Aleph::Gen_Polynomial< Coefficient >::Gen_Polynomial(), Aleph::Gen_Polynomial< Coefficient >::add_to_coeff(), Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Polynomial< Coefficient >::is_zero(), and Aleph::Gen_Polynomial< Coefficient >::num_terms().

◆ operator*=() [1/2]

template<typename Coefficient = double>

Gen_Polynomial & Aleph::Gen_Polynomial< Coefficient >::operator*= ( const Coefficient & s )

inline

In-place scalar multiplication.

Definition at line 873 of file tpl_polynomial.H.

References Aleph::Gen_Polynomial< Coefficient >::scale_inplace().

◆ operator*=() [2/2]

template<typename Coefficient = double>

Gen_Polynomial & Aleph::Gen_Polynomial< Coefficient >::operator*= ( const Gen_Polynomial< Coefficient > & q )

inline

In-place multiplication.

Definition at line 850 of file tpl_polynomial.H.

◆ operator+() [1/2]

template<typename Coefficient = double>

Gen_Polynomial Aleph::Gen_Polynomial< Coefficient >::operator+ ( const Coefficient & c ) const

inline

Add a scalar constant term.

Definition at line 763 of file tpl_polynomial.H.

◆ operator+() [2/2]

template<typename Coefficient = double>

Gen_Polynomial Aleph::Gen_Polynomial< Coefficient >::operator+ ( const Gen_Polynomial< Coefficient > & q ) const

inline

Polynomial addition.

Definition at line 738 of file tpl_polynomial.H.

◆ operator+=() [1/2]

template<typename Coefficient = double>

Gen_Polynomial & Aleph::Gen_Polynomial< Coefficient >::operator+= ( const Coefficient & c )

inline

In-place addition of a scalar constant term.

Definition at line 771 of file tpl_polynomial.H.

References Aleph::Gen_Polynomial< Coefficient >::add_to_coeff().

◆ operator+=() [2/2]

template<typename Coefficient = double>

Gen_Polynomial & Aleph::Gen_Polynomial< Coefficient >::operator+= ( const Gen_Polynomial< Coefficient > & q )

inline

In-place addition.

Definition at line 746 of file tpl_polynomial.H.

References Aleph::Gen_Polynomial< Coefficient >::add_to_coeff(), Aleph::Gen_Polynomial< Coefficient >::coeffs, Aleph::divide_and_conquer_partition_dp(), and Aleph::Gen_Polynomial< Coefficient >::scale_inplace().

◆ operator-() [1/3]

template<typename Coefficient = double>

Gen_Polynomial Aleph::Gen_Polynomial< Coefficient >::operator- ( ) const

inline

Unary negation.

Definition at line 726 of file tpl_polynomial.H.

References Aleph::Gen_Polynomial< Coefficient >::coeffs.

◆ operator-() [2/3]

template<typename Coefficient = double>

Gen_Polynomial Aleph::Gen_Polynomial< Coefficient >::operator- ( const Coefficient & c ) const

inline

Subtract a scalar constant term.

Definition at line 803 of file tpl_polynomial.H.

◆ operator-() [3/3]

template<typename Coefficient = double>

Gen_Polynomial Aleph::Gen_Polynomial< Coefficient >::operator- ( const Gen_Polynomial< Coefficient > & q ) const

inline

Polynomial subtraction.

Definition at line 778 of file tpl_polynomial.H.

◆ operator-=() [1/2]

template<typename Coefficient = double>

Gen_Polynomial & Aleph::Gen_Polynomial< Coefficient >::operator-= ( const Coefficient & c )

inline

In-place subtraction of a scalar constant term.

Definition at line 811 of file tpl_polynomial.H.

References Aleph::Gen_Polynomial< Coefficient >::add_to_coeff().

◆ operator-=() [2/2]

template<typename Coefficient = double>

Gen_Polynomial & Aleph::Gen_Polynomial< Coefficient >::operator-= ( const Gen_Polynomial< Coefficient > & q )

inline

In-place subtraction.

Definition at line 786 of file tpl_polynomial.H.

References Aleph::Gen_Polynomial< Coefficient >::add_to_coeff(), Aleph::Gen_Polynomial< Coefficient >::coeffs, and Aleph::divide_and_conquer_partition_dp().

◆ operator/() [1/2]

template<typename Coefficient = double>

Gen_Polynomial Aleph::Gen_Polynomial< Coefficient >::operator/ ( const Coefficient & s ) const

inline

Divide by a scalar.

Exceptions

std::domain_error if s is zero.

Definition at line 882 of file tpl_polynomial.H.

References ah_domain_error_if, Aleph::Gen_Polynomial< Coefficient >::coeff_is_zero(), Aleph::Gen_Polynomial< Coefficient >::coeffs, and Aleph::divide_and_conquer_partition_dp().

◆ operator/() [2/2]

template<typename Coefficient = double>

Gen_Polynomial Aleph::Gen_Polynomial< Coefficient >::operator/ ( const Gen_Polynomial< Coefficient > & d ) const

inline

Polynomial quotient.

Definition at line 950 of file tpl_polynomial.H.

References Aleph::Gen_Polynomial< Coefficient >::divmod().

◆ operator/=() [1/2]

template<typename Coefficient = double>

Gen_Polynomial & Aleph::Gen_Polynomial< Coefficient >::operator/= ( const Coefficient & s )

inline

In-place scalar division.

Definition at line 897 of file tpl_polynomial.H.

References Aleph::Gen_Polynomial< Coefficient >::divide_scalar_inplace().

◆ operator/=() [2/2]

template<typename Coefficient = double>

Gen_Polynomial & Aleph::Gen_Polynomial< Coefficient >::operator/= ( const Gen_Polynomial< Coefficient > & d )

inline

In-place polynomial quotient.

Definition at line 962 of file tpl_polynomial.H.

References Aleph::Gen_Polynomial< Coefficient >::divmod().

◆ operator==()

template<typename Coefficient = double>

bool Aleph::Gen_Polynomial< Coefficient >::operator== ( const Gen_Polynomial< Coefficient > & q ) const

inlinenoexcept

Equality comparison.

Two polynomials are equal iff they have the same non-zero terms. For floating-point types, coefficients are compared within epsilon.

Definition at line 1750 of file tpl_polynomial.H.

References Aleph::and, Aleph::Gen_Polynomial< Coefficient >::coeff_is_zero(), Aleph::Gen_Polynomial< Coefficient >::coeffs, and Aleph::divide_and_conquer_partition_dp().

◆ operator[]()

template<typename Coefficient = double>

Coefficient Aleph::Gen_Polynomial< Coefficient >::operator[] ( size_t exp ) const

inline

Coefficient at exponent exp (0 if absent).

Definition at line 588 of file tpl_polynomial.H.

References Aleph::Gen_Polynomial< Coefficient >::coeff_at(), and exp().

◆ positive_divisors()

template<typename Coefficient = double>

static DynList< Coefficient > Aleph::Gen_Polynomial< Coefficient >::positive_divisors ( Coefficient value )

inlinestatic

Definition at line 2198 of file tpl_polynomial.H.

References Aleph::polynomial_detail::abs_to_u64(), Aleph::DynList< T >::append(), and Aleph::divide_and_conquer_partition_dp().

Referenced by Aleph::Gen_Polynomial< Coefficient >::try_extract_primitive_cubic_factor(), Aleph::Gen_Polynomial< Coefficient >::try_extract_primitive_quadratic_factor(), and Aleph::Gen_Polynomial< Coefficient >::try_extract_rational_linear_factor().

◆ pow()

template<typename Coefficient = double>

Gen_Polynomial Aleph::Gen_Polynomial< Coefficient >::pow ( size_t n ) const

inline

Exponentiation \(p(x)^n\) by repeated squaring.

Parameters

[in] n Exponent.

Returns: \(p(x)^n\) (1 if n == 0).

Definition at line 1127 of file tpl_polynomial.H.

References Aleph::divide_and_conquer_partition_dp().

Referenced by algebraic_transformations(), Aleph::Gen_Polynomial< Coefficient >::compose(), TEST(), TEST(), and TEST().

◆ primitive_part()

template<typename Coefficient = double>

Gen_Polynomial Aleph::Gen_Polynomial< Coefficient >::primitive_part ( ) const

inline

Primitive part: polynomial divided by its content.

Returns \(p / \text{content}(p)\). For a non-zero polynomial, the result has leading coefficient positive (in absolute value).

Note: Only available for integral coefficient types.

Returns: A polynomial with gcd of coefficients = 1 (or zero poly).

Definition at line 1987 of file tpl_polynomial.H.

References Aleph::Gen_Polynomial< Coefficient >::Gen_Polynomial(), Aleph::Gen_Polynomial< Coefficient >::coeffs, Aleph::Gen_Polynomial< Coefficient >::content(), Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Polynomial< Coefficient >::is_zero(), Aleph::Gen_Polynomial< Coefficient >::leading_coeff(), and Aleph::Gen_Polynomial< Coefficient >::scale_inplace().

Referenced by Aleph::Gen_Polynomial< Coefficient >::factorize(), Aleph::Gen_Polynomial< Coefficient >::integer_gcd(), TEST(), TEST(), TEST(), Aleph::Gen_Polynomial< Coefficient >::try_extract_primitive_cubic_factor(), Aleph::Gen_Polynomial< Coefficient >::try_extract_primitive_quadratic_factor(), and Aleph::Gen_Polynomial< Coefficient >::yun_sfd().

◆ pseudo_divmod()

template<typename Coefficient = double>

std::pair< Gen_Polynomial, Gen_Polynomial > Aleph::Gen_Polynomial< Coefficient >::pseudo_divmod ( const Gen_Polynomial< Coefficient > & d ) const

inline

Pseudo-division for non-field coefficient types.

Computes q, r such that \(\text{lc}(d)^{\deg(a)-\deg(d)+1} \cdot a = q \cdot d + r\). No division of coefficients is performed, so this works correctly over integer rings.

Parameters

[in] d Divisor (must not be zero).

Returns: Pair (quotient, remainder).

Exceptions

std::domain_error if d is zero.

Definition at line 1240 of file tpl_polynomial.H.

References Aleph::Gen_Polynomial< Coefficient >::Gen_Polynomial(), Aleph::Gen_Polynomial< Coefficient >::add_to_coeff(), ah_domain_error_if, Aleph::Gen_Polynomial< Coefficient >::degree(), Aleph::divide_and_conquer_partition_dp(), exp(), Aleph::Gen_Polynomial< Coefficient >::is_zero(), Aleph::Gen_Polynomial< Coefficient >::leading_coeff(), Aleph::polynomial_detail::power(), r, and Aleph::Gen_Polynomial< Coefficient >::scale_inplace().

Referenced by Aleph::Gen_Polynomial< Coefficient >::integer_gcd(), and TEST().

◆ reduce_coeffs_mod()

template<typename Coefficient = double>

static Gen_Polynomial Aleph::Gen_Polynomial< Coefficient >::reduce_coeffs_mod	(	const Gen_Polynomial< Coefficient > &	f,
		Coefficient	mod
	)

inlinestatic

Definition at line 2135 of file tpl_polynomial.H.

References Aleph::divide_and_conquer_partition_dp(), exp(), and Aleph::Gen_Polynomial< Coefficient >::for_each_term().

Referenced by Aleph::Gen_Polynomial< Coefficient >::factor_mod_p().

◆ remove_zeros()

template<typename Coefficient = double>

void Aleph::Gen_Polynomial< Coefficient >::remove_zeros ( )

inlineprivate

Remove all entries whose coefficient is (approximately) zero.

Definition at line 204 of file tpl_polynomial.H.

References Aleph::DynList< T >::append(), Aleph::Gen_Polynomial< Coefficient >::coeff_is_zero(), Aleph::Gen_Polynomial< Coefficient >::coeffs, and FunctionalMethods< Container, T >::for_each().

◆ reverse()

template<typename Coefficient = double>

Gen_Polynomial Aleph::Gen_Polynomial< Coefficient >::reverse ( ) const

inline

Reciprocal polynomial: \(x^d \cdot p(1/x)\).

Reverses the coefficient sequence. If \(p(x) = \sum c_i x^i\), the reciprocal is \(\sum c_i x^{d-i}\) where \(d = \deg(p)\).

Definition at line 1303 of file tpl_polynomial.H.

References Aleph::Gen_Polynomial< Coefficient >::Gen_Polynomial(), Aleph::Gen_Polynomial< Coefficient >::coeffs, Aleph::Gen_Polynomial< Coefficient >::degree(), and Aleph::Gen_Polynomial< Coefficient >::is_zero().

Referenced by algebraic_transformations(), and TEST().

◆ scale_inplace()

template<typename Coefficient = double>

void Aleph::Gen_Polynomial< Coefficient >::scale_inplace ( const Coefficient & s )

inlineprivate

Multiply every coefficient in place by a scalar.

Definition at line 269 of file tpl_polynomial.H.

References Aleph::DynList< T >::append(), Aleph::Gen_Polynomial< Coefficient >::coeff_is_zero(), Aleph::Gen_Polynomial< Coefficient >::coeffs, Aleph::divide_and_conquer_partition_dp(), exp(), and FunctionalMethods< Container, T >::for_each().

Referenced by Aleph::Gen_Polynomial< Coefficient >::operator*=(), Aleph::Gen_Polynomial< Coefficient >::operator+=(), Aleph::Gen_Polynomial< Coefficient >::primitive_part(), and Aleph::Gen_Polynomial< Coefficient >::pseudo_divmod().

◆ set_coeff()

template<typename Coefficient = double>

void Aleph::Gen_Polynomial< Coefficient >::set_coeff	(	size_t	exp,
		const Coefficient &	c
	)

inline

Set coefficient at exponent; removes entry if zero.

Parameters

[in]	exp	Exponent of the term.
[in]	c	The coefficient value.

Definition at line 1934 of file tpl_polynomial.H.

References Aleph::Gen_Polynomial< Coefficient >::coeff_is_zero(), Aleph::Gen_Polynomial< Coefficient >::coeff_ptr(), Aleph::Gen_Polynomial< Coefficient >::coeffs, Aleph::divide_and_conquer_partition_dp(), and exp().

◆ shift()

template<typename Coefficient = double>

Gen_Polynomial Aleph::Gen_Polynomial< Coefficient >::shift ( const Coefficient & k ) const

inline

Taylor shift: \(p(x + k)\).

Computed via composition with the linear polynomial \(x + k\).

Parameters

[in] k Shift amount.

Returns: The polynomial \(p(x + k)\).

Note: Delegates to compose and therefore benefits from the sparse-aware composition path.

Definition at line 1342 of file tpl_polynomial.H.

References Aleph::Gen_Polynomial< Coefficient >::Gen_Polynomial(), Aleph::Gen_Polynomial< Coefficient >::compose(), Aleph::divide_and_conquer_partition_dp(), and k.

Referenced by Aleph::Gen_Polynomial< Coefficient >::add_scaled_shifted(), algebraic_transformations(), Aleph::Gen_Polynomial< Coefficient >::divmod(), TEST(), and TEST().

◆ shift_down()

template<typename Coefficient = double>

Gen_Polynomial Aleph::Gen_Polynomial< Coefficient >::shift_down ( size_t k ) const

inline

Divide by \(x^k\) (shift exponents down).

Terms with exponent less than k are discarded (floor division).

Parameters

[in] k Number of positions to shift down.

Returns: \(\lfloor p(x) / x^k \rfloor\).

Definition at line 1372 of file tpl_polynomial.H.

References Aleph::Gen_Polynomial< Coefficient >::coeffs, and k.

Referenced by TEST(), TEST(), and TEST().

◆ shift_up()

template<typename Coefficient = double>

Gen_Polynomial Aleph::Gen_Polynomial< Coefficient >::shift_up ( size_t k ) const

inline

Multiply by \(x^k\) (shift exponents up).

Parameters

[in] k Number of positions to shift up.

Returns: \(x^k \cdot p(x)\).

Definition at line 1352 of file tpl_polynomial.H.

References Aleph::Gen_Polynomial< Coefficient >::coeffs, and k.

Referenced by TEST(), and TEST().

◆ sign_variations()

template<typename Coefficient = double>

size_t Aleph::Gen_Polynomial< Coefficient >::sign_variations ( ) const

inline

Count sign changes in the coefficient sequence.

By Descartes' rule, the number of positive real roots (with multiplicity) is at most the number of sign changes and has the same parity.

Returns: Number of sign changes.

Definition at line 1504 of file tpl_polynomial.H.

References Aleph::and, Aleph::Gen_Polynomial< Coefficient >::coeffs, Aleph::divide_and_conquer_partition_dp(), and Aleph::Gen_Polynomial< Coefficient >::epsilon().

Referenced by root_analysis(), and TEST().

◆ sparse_eval()

template<typename Coefficient = double>

Coefficient Aleph::Gen_Polynomial< Coefficient >::sparse_eval ( const Coefficient & x ) const

inline

Evaluate \(p(x)\) using sparse evaluation.

Each non-zero term \(c \cdot x^e\) is computed via fast exponentiation. Complexity: \(O(k \log d)\) where \(k\) is the number of terms and \(d\) is the degree.

Parameters

[in] x Evaluation point.

Returns: \(p(x)\).

Definition at line 663 of file tpl_polynomial.H.

References Aleph::Gen_Polynomial< Coefficient >::coeffs, Aleph::divide_and_conquer_partition_dp(), and Aleph::polynomial_detail::power().

Referenced by Aleph::Gen_Polynomial< Coefficient >::eval().

◆ square_free()

template<typename Coefficient = double>

Gen_Polynomial Aleph::Gen_Polynomial< Coefficient >::square_free ( ) const

inline

Square-free part: \(p / \gcd(p, p')\).

Removes repeated root factors. For example, if \(p(x) = (x-1)^3 (x-2)\), the square-free part is \((x-1)(x-2)\).

Returns: A polynomial with no repeated roots.

Note: Requires coefficient type to form a field.; Complexity: dominated by the GCD computation, \(O(d^2)\) polynomial divisions.

Definition at line 1437 of file tpl_polynomial.H.

References Aleph::Gen_Polynomial< Coefficient >::derivative(), Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Polynomial< Coefficient >::gcd(), Aleph::Gen_Polynomial< Coefficient >::is_constant(), and Aleph::Gen_Polynomial< Coefficient >::is_zero().

Referenced by algebraic_transformations(), TEST(), and TEST().

◆ sturm_chain()

template<typename Coefficient = double>

DynList< Gen_Polynomial > Aleph::Gen_Polynomial< Coefficient >::sturm_chain ( ) const

inline

Sturm sequence of this polynomial.

The Sturm chain \(p_0 = p, p_1 = p', p_{i+1} = -\text{rem}(p_{i-1}, p_i)\) is used to count distinct real roots in an interval.

Returns: DynList of polynomials forming the Sturm chain.

Note: Complexity: \(O(d^2)\) where \(d = \deg(p)\), dominated by the sequence of polynomial remainders.

Definition at line 1549 of file tpl_polynomial.H.

References Aleph::DynList< T >::append(), Aleph::Gen_Polynomial< Coefficient >::derivative(), Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Polynomial< Coefficient >::is_constant(), Aleph::Gen_Polynomial< Coefficient >::is_zero(), and r.

Referenced by Aleph::Gen_Polynomial< Coefficient >::count_real_roots(), and TEST().

◆ sturm_sign_changes()

template<typename Coefficient = double>

static size_t Aleph::Gen_Polynomial< Coefficient >::sturm_sign_changes	(	const DynList< Gen_Polynomial< Coefficient > > &	chain,
		const Coefficient &	x
	)

inlinestatic

Count sign changes in a Sturm chain at a given point.

Parameters

[in]	chain	Sturm chain (from sturm_chain()).
[in]	x	Evaluation point.

Returns: Number of sign changes in the sequence \(p_0(x), p_1(x), \ldots\).

Definition at line 1579 of file tpl_polynomial.H.

References Aleph::and, Aleph::Gen_Polynomial< Coefficient >::coeff_is_zero(), and Aleph::divide_and_conquer_partition_dp().

Referenced by Aleph::Gen_Polynomial< Coefficient >::count_real_roots().

◆ terms_list()

template<typename Coefficient = double>

DynList< std::pair< size_t, Coefficient > > Aleph::Gen_Polynomial< Coefficient >::terms_list ( ) const

inline

All non-zero terms as a sorted list of (exponent, coefficient).

Definition at line 1827 of file tpl_polynomial.H.

References Aleph::DynList< T >::append(), and Aleph::Gen_Polynomial< Coefficient >::coeffs.

Referenced by TEST().

◆ to_dense()

template<typename Coefficient = double>

Array< Coefficient > Aleph::Gen_Polynomial< Coefficient >::to_dense ( ) const

inline

Dense coefficient vector.

Returns an Array of size \(d + 1\) (or empty for zero polynomial) containing all coefficients in ascending exponent order, zero-filled for absent terms.

Definition at line 1411 of file tpl_polynomial.H.

References Aleph::Gen_Polynomial< Coefficient >::coeffs, Aleph::Gen_Polynomial< Coefficient >::degree(), Aleph::divide_and_conquer_partition_dp(), and Aleph::Gen_Polynomial< Coefficient >::is_zero().

Referenced by TEST(), and TEST().

◆ to_monic()

template<typename Coefficient = double>

Gen_Polynomial Aleph::Gen_Polynomial< Coefficient >::to_monic ( ) const

inline

Make monic: divide by leading coefficient.

Returns: Monic version of this polynomial.

Exceptions

std::domain_error if zero polynomial.

Definition at line 1292 of file tpl_polynomial.H.

References ah_domain_error_if, Aleph::Gen_Polynomial< Coefficient >::is_zero(), and Aleph::Gen_Polynomial< Coefficient >::leading_coeff().

Referenced by TEST().

◆ to_str()

template<typename Coefficient = double>

std::string Aleph::Gen_Polynomial< Coefficient >::to_str ( const std::string & var = "x" ) const

inline

Human-readable string representation.

Uses descending exponent order with mathematical sign conventions: "3x^2 + 2x - 1", "x^3 - x", "5", "0".

Parameters

[in] var Variable name (default "x").

Definition at line 1861 of file tpl_polynomial.H.

References Aleph::Gen_Polynomial< Coefficient >::coeffs, Aleph::divide_and_conquer_partition_dp(), exp(), and Aleph::Gen_Polynomial< Coefficient >::for_each_term_desc().

Referenced by Aleph::operator<<(), TEST(), TEST(), and TEST().

◆ truncate()

template<typename Coefficient = double>

Gen_Polynomial Aleph::Gen_Polynomial< Coefficient >::truncate ( size_t n ) const

inline

Truncate to degree less than n.

Keeps only terms with exponent strictly less than n, i.e., computes \(p(x) \bmod x^n\).

Parameters

[in] n Truncation order.

Definition at line 1393 of file tpl_polynomial.H.

References Aleph::Gen_Polynomial< Coefficient >::coeffs.

Referenced by TEST(), TEST(), and TEST().

◆ try_divide_by_linear_factor()

template<typename Coefficient = double>

static bool Aleph::Gen_Polynomial< Coefficient >::try_divide_by_linear_factor	(	const Gen_Polynomial< Coefficient > &	f,
		Coefficient	a,
		Coefficient	b,
		Gen_Polynomial< Coefficient > &	quotient
	)

inlinestatic

Definition at line 2245 of file tpl_polynomial.H.

References Aleph::Gen_Polynomial< Coefficient >::Gen_Polynomial(), Aleph::Gen_Polynomial< Coefficient >::degree(), Aleph::divide_and_conquer_partition_dp(), exp(), and k.

Referenced by Aleph::Gen_Polynomial< Coefficient >::factorize(), and Aleph::Gen_Polynomial< Coefficient >::try_extract_rational_linear_factor().

◆ try_exact_candidate_division()

template<typename Coefficient = double>

static bool Aleph::Gen_Polynomial< Coefficient >::try_exact_candidate_division	(	const Gen_Polynomial< Coefficient > &	f,
		const Gen_Polynomial< Coefficient > &	candidate,
		Gen_Polynomial< Coefficient > &	quotient
	)

inlinestatic

Try exact division but treat inexact integral division as a rejected candidate.

Exhaustive integer factor searches intentionally test many polynomials that are not actual divisors. After hardening divmod() to throw on inexact leading-coefficient division, these search paths must convert that condition back into a simple "candidate does not divide" result.

Definition at line 2226 of file tpl_polynomial.H.

References Aleph::divide_and_conquer_partition_dp(), and r.

Referenced by Aleph::Gen_Polynomial< Coefficient >::try_extract_primitive_cubic_factor(), and Aleph::Gen_Polynomial< Coefficient >::try_extract_primitive_quadratic_factor().

◆ try_extract_primitive_cubic_factor()

template<typename Coefficient = double>

static bool Aleph::Gen_Polynomial< Coefficient >::try_extract_primitive_cubic_factor	(	const Gen_Polynomial< Coefficient > &	f,
		Gen_Polynomial< Coefficient > &	factor,
		Gen_Polynomial< Coefficient > &	quotient
	)

inlinestatic

Try to extract an exact primitive cubic factor over \(\mathbb{Z}\).

Exhaustively searches primitive cubic candidates \(a x^3 + b x^2 + c x + d\) such that \(a\) divides the leading coefficient and \(d\) divides the constant term. Candidate coefficients are bounded with a Landau-Mignotte style estimate, and each candidate is verified by exact division.

Definition at line 2424 of file tpl_polynomial.H.

References Aleph::polynomial_detail::abs_to_u64(), Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Polynomial< Coefficient >::is_zero(), Aleph::Gen_Polynomial< Coefficient >::positive_divisors(), Aleph::Gen_Polynomial< Coefficient >::primitive_part(), Aleph::Gen_Polynomial< Coefficient >::set_coeff(), and Aleph::Gen_Polynomial< Coefficient >::try_exact_candidate_division().

Referenced by Aleph::Gen_Polynomial< Coefficient >::factorize().

◆ try_extract_primitive_quadratic_factor()

template<typename Coefficient = double>

static bool Aleph::Gen_Polynomial< Coefficient >::try_extract_primitive_quadratic_factor	(	const Gen_Polynomial< Coefficient > &	f,
		Gen_Polynomial< Coefficient > &	factor,
		Gen_Polynomial< Coefficient > &	quotient
	)

inlinestatic

Try to extract an exact primitive quadratic factor over \(\mathbb{Z}\).

Exhaustively searches primitive quadratic candidates \(a x^2 + b x + c\) such that \(a\) divides the leading coefficient and \(c\) divides the constant term. Candidate linear coefficients are bounded using a Cauchy-style root bound and verified by exact polynomial division.

Definition at line 2343 of file tpl_polynomial.H.

References Aleph::polynomial_detail::abs_to_u64(), Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Polynomial< Coefficient >::is_zero(), Aleph::Gen_Polynomial< Coefficient >::positive_divisors(), Aleph::Gen_Polynomial< Coefficient >::primitive_part(), Aleph::Gen_Polynomial< Coefficient >::set_coeff(), and Aleph::Gen_Polynomial< Coefficient >::try_exact_candidate_division().

Referenced by Aleph::Gen_Polynomial< Coefficient >::factorize().

◆ try_extract_rational_linear_factor()

template<typename Coefficient = double>

static bool Aleph::Gen_Polynomial< Coefficient >::try_extract_rational_linear_factor	(	const Gen_Polynomial< Coefficient > &	f,
		Gen_Polynomial< Coefficient > &	factor,
		Gen_Polynomial< Coefficient > &	quotient
	)

inlinestatic

Definition at line 2285 of file tpl_polynomial.H.

References Aleph::Gen_Polynomial< Coefficient >::Gen_Polynomial(), Aleph::polynomial_detail::abs_to_u64(), Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Polynomial< Coefficient >::positive_divisors(), and Aleph::Gen_Polynomial< Coefficient >::try_divide_by_linear_factor().

Referenced by Aleph::Gen_Polynomial< Coefficient >::factorize().

◆ x_to()

template<typename Coefficient = double>

static Gen_Polynomial Aleph::Gen_Polynomial< Coefficient >::x_to ( size_t n )

inlinestatic

The monomial \(x^n\).

Parameters

[in] n Exponent.

Definition at line 455 of file tpl_polynomial.H.

References Aleph::Gen_Polynomial< Coefficient >::Gen_Polynomial(), and Aleph::divide_and_conquer_partition_dp().

Referenced by TEST().

◆ xgcd()

template<typename Coefficient = double>

static Xgcd_Result Aleph::Gen_Polynomial< Coefficient >::xgcd	(	Gen_Polynomial< Coefficient >	a,
		Gen_Polynomial< Coefficient >	b
	)

inlinestatic

Definition at line 1184 of file tpl_polynomial.H.

References Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Polynomial< Coefficient >::divmod(), Aleph::Gen_Polynomial< Coefficient >::is_zero(), Aleph::Gen_Polynomial< Coefficient >::leading_coeff(), and r.

Referenced by algebraic_transformations(), TEST(), and TEST().

◆ yun_sfd()

template<typename Coefficient = double>

DynList< SfdTerm > Aleph::Gen_Polynomial< Coefficient >::yun_sfd ( ) const

inline

Yun's square-free decomposition (SFD).

Decomposes a polynomial into square-free factors with multiplicities. Each factor has no repeated roots, and the union of all factors (with multiplicity) reconstructs the original.

Uses Yun's algorithm:

Compute \(f' = \text{derivative}(f)\).
Iteratively remove common factors to extract multiplicities.

Returns: A list of SfdTerm, each with a square-free factor and its multiplicity. Empty list if polynomial is constant.

Note: Complexity: \(O(d^2)\) GCD operations.

Definition at line 2065 of file tpl_polynomial.H.

References Aleph::Gen_Polynomial< Coefficient >::_integer_exact_quot(), Aleph::DynList< T >::append(), Aleph::Gen_Polynomial< Coefficient >::derivative(), Aleph::divide_and_conquer_partition_dp(), h, Aleph::Gen_Polynomial< Coefficient >::integer_gcd(), Aleph::Gen_Polynomial< Coefficient >::is_constant(), Aleph::Gen_Polynomial< Coefficient >::primitive_part(), and w.

Referenced by TEST(), TEST(), TEST(), TEST(), and TEST().

◆ zero()

template<typename Coefficient = double>

static Gen_Polynomial Aleph::Gen_Polynomial< Coefficient >::zero ( )

inlinestatic

The zero polynomial.

Definition at line 441 of file tpl_polynomial.H.

References Aleph::Gen_Polynomial< Coefficient >::Gen_Polynomial().

Referenced by TEST().

Member Data Documentation

◆ coeffs

template<typename Coefficient = double>

DynMapTree<size_t, Coefficient> Aleph::Gen_Polynomial< Coefficient >::coeffs

private

Definition at line 173 of file tpl_polynomial.H.

The documentation for this class was generated from the following file:

tpl_polynomial.H

Classes

Public Types

Public Member Functions

Static Public Member Functions

Private Types

Private Member Functions

Static Private Member Functions

Private Attributes

Detailed Description

Member Typedef Documentation

◆ Coeff

◆ Term

Constructor & Destructor Documentation

◆ Gen_Polynomial() [1/6]

◆ Gen_Polynomial() [2/6]

◆ Gen_Polynomial() [3/6]

◆ Gen_Polynomial() [4/6]

◆ Gen_Polynomial() [5/6]

◆ Gen_Polynomial() [6/6]

Member Function Documentation

◆ _integer_exact_quot()

◆ add_scaled_shifted()

◆ add_to_coeff()

◆ bisect_root()

◆ cauchy_bound()

◆ coeff_at()

◆ coeff_is_zero()

◆ coeff_ptr() [1/2]

◆ coeff_ptr() [2/2]

◆ coefficients()

◆ compose()

◆ content()

◆ count_all_real_roots()

◆ count_real_roots()

◆ definite_integral()

◆ degree()

◆ derivative()

◆ divide_by_monic_linear_mod()

◆ divide_scalar_inplace()

◆ divmod()

◆ epsilon()

◆ eval()

◆ eval_mod_u64()

◆ exponents()

◆ factor_mod_p()

◆ factorize()

◆ for_each_term()

◆ for_each_term_desc()

◆ from_roots()

◆ gcd()

◆ get_coeff()

◆ has_term()

◆ hensel_lift()

◆ horner_eval()

◆ integer_gcd()

◆ integral()

◆ interpolate()

◆ is_constant()

◆ is_monic()

◆ is_monomial()

◆ is_zero()

◆ lcm()

◆ leading_coeff()

◆ mignotte_bound()

◆ multi_eval()

◆ multiply_by_monic_linear()

◆ negate_arg()

◆ newton_root()

◆ nth_derivative()

◆ num_terms()

◆ one()

◆ operator!=()

◆ operator%()

◆ operator%=()

◆ operator()()

◆ operator*() [1/2]

◆ operator*() [2/2]

◆ operator*=() [1/2]

◆ operator*=() [2/2]

◆ operator+() [1/2]