tpl_polynomial.H File Reference

Univariate polynomial ring arithmetic over generic coefficients. More...

#include <cmath>
#include <initializer_list>
#include <limits>
#include <sstream>
#include <string>
#include <type_traits>
#include <utility>
#include <numeric>
#include <random>
#include <ah-errors.H>
#include <tpl_dynMapTree.H>
#include <tpl_array.H>
#include <htlist.H>
#include <modular_arithmetic.H>

Include dependency graph for tpl_polynomial.H:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
class	Aleph::Gen_Polynomial< Coefficient >
	Univariate polynomial over a generic coefficient ring. More...
struct	Aleph::Gen_Polynomial< Coefficient >::Xgcd_Result
	Extended GCD: computes g, s, t such that \(sa + tb = g\). More...
struct	Aleph::Gen_Polynomial< Coefficient >::SfdTerm
	Square-free decomposition term: factor and multiplicity. More...

Namespaces
namespace	Aleph
	Main namespace for Aleph-w library functions.
namespace	Aleph::polynomial_detail
	Internal helpers for polynomial operations.

Typedefs
using	Aleph::Polynomial = Gen_Polynomial< double >
	Polynomial with double coefficients.
using	Aleph::PolynomialF = Gen_Polynomial< float >
	Polynomial with float coefficients.
using	Aleph::PolynomialLD = Gen_Polynomial< long double >
	Polynomial with long double coefficients.
using	Aleph::IntPolynomial = Gen_Polynomial< long long >
	Polynomial with long long (integer) coefficients.

Functions
template<typename C >
C	Aleph::polynomial_detail::power (C base, size_t exp)
	Fast exponentiation by squaring.
template<typename Int > requires std::is_integral_v<Int>
uint64_t	Aleph::polynomial_detail::abs_to_u64 (Int value) noexcept
template<typename Int > requires std::is_integral_v<Int>
uint64_t	Aleph::polynomial_detail::normalize_mod_u64 (Int value, const uint64_t modulus) noexcept
template<typename Int > requires std::is_integral_v<Int>
Int	Aleph::polynomial_detail::centered_from_mod_u64 (const uint64_t value, const uint64_t modulus) noexcept
template<typename C >
Gen_Polynomial< C >	Aleph::operator* (const C &s, const Gen_Polynomial< C > &p)
	Scalar times polynomial (commutative form).
template<typename C >
Gen_Polynomial< C >	Aleph::operator+ (const C &s, const Gen_Polynomial< C > &p)
	Scalar plus polynomial (commutative form).
template<typename C >
Gen_Polynomial< C >	Aleph::operator- (const C &s, const Gen_Polynomial< C > &p)
	Scalar minus polynomial.
template<typename C >
std::ostream &	Aleph::operator<< (std::ostream &out, const Gen_Polynomial< C > &p)
	Stream output.

Detailed Description

Univariate polynomial ring arithmetic over generic coefficients.

Provides Gen_Polynomial<Coefficient>, a sparse univariate polynomial backed by DynMapTree<size_t, Coefficient>. Only non-zero coefficients are stored, making operations efficient on high-degree sparse polynomials such as \(x^{1000} + 1\).

The coefficient type must satisfy:

• Default-constructible (yielding the additive identity, zero).
• Constructible from int literals 0 and 1.
• Copy/move constructible and assignable.
• Arithmetic: +, - (binary and unary), *, /.
• Comparison: ==, !=.
• Ordered comparison < (needed by cauchy_bound, sign_variations, bisect_root, and to_str).
• Stream output: operator<<.

For floating-point types, std::abs is used internally for epsilon-based zero detection.

Author

Leandro Rabindranath León

Definition in file tpl_polynomial.H.