pub struct PolyOver<K> { /* private fields */ }Expand description
A polynomial in one variable over K, little-endian, no trailing zero.
Implementations§
Source§impl<K: OrderedField> PolyOver<K>
impl<K: OrderedField> PolyOver<K>
pub fn from(c: Vec<K>) -> PolyOver<K>
pub fn constant(a: K) -> PolyOver<K>
pub fn zero() -> PolyOver<K>
pub fn one() -> PolyOver<K>
pub fn is_zero(&self) -> bool
pub fn degree(&self) -> Option<usize>
pub fn coeff(&self, i: usize) -> K
pub fn add(&self, o: &PolyOver<K>) -> PolyOver<K>
pub fn neg(&self) -> PolyOver<K>
pub fn mul(&self, o: &PolyOver<K>) -> PolyOver<K>
pub fn scale(&self, k: &K) -> PolyOver<K>
Sourcepub fn div_rem(&self, d: &PolyOver<K>) -> (PolyOver<K>, PolyOver<K>)
pub fn div_rem(&self, d: &PolyOver<K>) -> (PolyOver<K>, PolyOver<K>)
Euclid’s division by a nonzero d: (q, r) with self = q·d + r and deg r < deg d.
pub fn monic(&self) -> PolyOver<K>
pub fn derivative(&self) -> PolyOver<K>
Sourcepub fn squarefree_parts(&self) -> (K, Vec<(PolyOver<K>, usize)>)
pub fn squarefree_parts(&self) -> (K, Vec<(PolyOver<K>, usize)>)
lc · Π aᵢ^i with each aᵢ monic and squarefree and the aᵢ coprime, by Yun’s algorithm:
the leading coefficient and each (aᵢ, i) of positive degree.
pub fn eval(&self, t: &K) -> K
Sourcepub fn squarefree(&self) -> PolyOver<K>
pub fn squarefree(&self) -> PolyOver<K>
The squarefree part, monic: self / gcd(self, self′).
Sourcepub fn without_zero_root(&self) -> PolyOver<K>
pub fn without_zero_root(&self) -> PolyOver<K>
self / x^k for the largest k that divides it: the polynomial without its root 0.
Sourcepub fn reversed(&self) -> PolyOver<K>
pub fn reversed(&self) -> PolyOver<K>
x^n·self(1/x) for n the degree: the polynomial whose roots are the reciprocals of the
nonzero roots.
Sourcepub fn resultant(&self, o: &PolyOver<K>) -> K
pub fn resultant(&self, o: &PolyOver<K>) -> K
The resultant lc^{deg o}·Π o(α) over the roots α of self, by Euclid’s algorithm.
Sourcepub fn interpolate(degree: usize, at: impl Fn(i64) -> K) -> PolyOver<K>
pub fn interpolate(degree: usize, at: impl Fn(i64) -> K) -> PolyOver<K>
The polynomial of degree at most degree whose value at each integer j ≤ degree is
at(j), by Newton’s divided differences.
Sourcepub fn sum_poly(p: &PolyOver<K>, q: &PolyOver<K>) -> PolyOver<K>
pub fn sum_poly(p: &PolyOver<K>, q: &PolyOver<K>) -> PolyOver<K>
The monic polynomial whose roots are the sums rᵢ + sⱼ of a root of each, every pair once —
Res_z(P(z), Q(y − z)) up to its leading coefficient — through power sums: the sums’ m-th power
sum is Σ_k C(m, k)·p_k(P)·p_(m−k)(Q).
Sourcepub fn product_poly(p: &PolyOver<K>, q: &PolyOver<K>) -> PolyOver<K>
pub fn product_poly(p: &PolyOver<K>, q: &PolyOver<K>) -> PolyOver<K>
The monic polynomial whose roots are the products rᵢ·sⱼ of a root of each, every pair once —
Res_z(P(z), z^n·Q(y/z)) up to its leading coefficient — through power sums: the products’
m-th power sum is p_m(P)·p_m(Q).
Sourcepub fn pade(
series: &[K],
l: usize,
m: usize,
) -> Option<(PolyOver<K>, PolyOver<K>)>
pub fn pade( series: &[K], l: usize, m: usize, ) -> Option<(PolyOver<K>, PolyOver<K>)>
The rational function num/den of numerator degree at most l and denominator degree at most
m, den(0) ≠ 0, whose expansion at 0 begins with series (its first l + m + 1
coefficients), by the extended Euclidean algorithm on x^(l+m+1) and the truncated series;
None when no such function exists.
Sourcepub fn power_poly(p: &PolyOver<K>, k: u32) -> PolyOver<K>
pub fn power_poly(p: &PolyOver<K>, k: u32) -> PolyOver<K>
The monic polynomial whose roots are the k-th powers of the roots of P, each as often as in
P — Res_z(P(z), y − z^k) up to its leading coefficient. A binomial P = a·zⁿ + b, whose roots
are the n-th roots of c = −b/a, has their k-th powers the roots of y^(n/g) − c^(k/g) for
g = gcd(n, k), read off at once. Any other is read through the power sums of its roots: by
Newton’s identities the coefficients give s₁ … s_{dk}, the k-th powers have the power sums
s_k, s_{2k}, …, s_{dk}, and the same identities give their coefficients back — O(d²k) field
operations, no determinant.