Struct Polynomial

pub struct Polynomial<T> { /* private fields */ }

Polynomial ring $R[x]$

use num::Rational64;
use polynomial_ring::Polynomial;
let f = Polynomial::new(vec![3, 1, 4, 1, 5].into_iter().map(|x| Rational64::from_integer(x)).collect());
let g = Polynomial::new(vec![2, 7, 1].into_iter().map(|x| Rational64::from_integer(x)).collect());
let mut r = f.clone();
let q = r.division(&g);
assert_eq!(f, q * g + r);

Implementations

impl<T: Sized> Polynomial<T>

pub fn deg(&self) -> Option<usize>

The degree of the polynomial. This is the highest power, or None for the zero polynomial.

use polynomial_ring::Polynomial;
let p = Polynomial::new(vec![3, 2, 1]); // 3+2x+x^2
assert_eq!(p.deg(), Some(2));
let q = Polynomial::new(vec![0]); // 0
assert_eq!(q.deg(), None);

pub fn lc(&self) -> Option<&T>

The leading coefficent. This is the coeffient of the highest power, or None for the zero polynomial.

use polynomial_ring::Polynomial;
let p = Polynomial::new(vec![3, 2, 1]); // 3+2x+x^2
assert_eq!(p.lc(), Some(&1));
let q = Polynomial::new(vec![0]); // 0
assert_eq!(q.lc(), None);

pub fn coeffs(&self) -> &[T]

Get the coefficents.

use polynomial_ring::Polynomial;
let p = Polynomial::new(vec![3, 2, 1]); // 3+2x+x^2
assert_eq!(p.coeffs(), &[3, 2, 1]);
let q = Polynomial::new(vec![0]); // 0
assert_eq!(q.coeffs(), &[]);

impl<M: Sized + Zero> Polynomial<M>

pub fn new(coeff: Vec<M>) -> Self

Construct a polynomial from a Vec of coefficients.

use polynomial_ring::Polynomial;
let p = Polynomial::new(vec![3, 2, 1]);
assert_eq!(p.to_string(), "x^2+2*x+3");

pub fn from_monomial(coefficent: M, degree: usize) -> Self

Construct a monomial $cx^d$ from a coefficient and a degree ($c$=coefficent, $d$=degree).

use polynomial_ring::Polynomial;
let p = Polynomial::from_monomial(3, 2);
let q = Polynomial::new(vec![0, 0, 3]);
assert_eq!(p, q);

impl<R: Sized> Polynomial<R>

pub fn eval<'a>(&self, x: &'a R) -> R

where R: Sized + Zero + for<'x> AddAssign<&'x R> + MulAssign<&'a R>,

Evaluate a polynomial at some point, using Horner’s method.

use polynomial_ring::Polynomial;
let p = Polynomial::new(vec![3, 2, 1]); // 3+2x+x^2
assert_eq!(p.eval(&1), 6);
assert_eq!(p.eval(&2), 11);

pub fn derivative(&self) -> Self

where R: Sized + Zero + One + for<'x> AddAssign<&'x R> + for<'x> From<<&'x R as Mul>::Output>, for<'x> &'x R: Mul,

Calculate the derivative.

use polynomial_ring::{Polynomial, polynomial};
let p = polynomial![1i32, 2, 3, 2, 1]; // 1+2x+3x^2+2x^3+x^4
assert_eq!(p.derivative(), polynomial![2, 6, 6, 4]); // 2+6x+6x^2+4x^3

pub fn pseudo_division(&mut self, other: &Self) -> (R, Self)

where R: Sized + Clone + Zero + One + for<'x> AddAssign<&'x R> + for<'x> MulAssign<&'x R> + for<'x> From<<&'x R as Sub>::Output> + for<'x> From<<&'x R as Mul>::Output>, for<'x> &'x R: Sub + Mul,

Pseudo division.

Let $R$ be an integral domain. Let $f, g \in R[x]$, where $g \neq 0$. This function calculates $s \in R$, $q, r \in R[x]$ s.t. $sf=qg+r$, where $r=0$ or $\deg(r)<\deg(g)$.

use polynomial_ring::{polynomial, Polynomial};

let f = polynomial![1i32, 3, 1]; // 1+3x+x^2 ∈ Z[x]
let g = polynomial![5, 2]; // 5+2x ∈ Z[x]
let mut r = f.clone();
let (s, q) = r.pseudo_division(&g);
assert_eq!(f * s, q * g + r);

pub fn resultant(self, other: Self) -> R

where R: Sized + Clone + Zero + One + for<'x> AddAssign<&'x R> + for<'x> MulAssign<&'x R> + Neg<Output = R> + for<'x> From<<&'x R as Sub>::Output> + for<'x> From<<&'x R as Mul>::Output> + for<'x> From<<&'x R as Div>::Output>, for<'x> &'x R: Sub + Mul + Div,

Calculate the resultant

use polynomial_ring::{polynomial, Polynomial};

let f = polynomial![0i32, 2, 0, 1]; // 2x+x^3 ∈ Z[x]
let g = polynomial![2, 3, 5]; // 2+3x+5x^2 ∈ Z[x]
let r = f.resultant(g);
assert_eq!(r, 164);

pub fn primitive_part_mut(&mut self)

where R: Sized + Clone + Zero + for<'x> DivAssign<&'x R> + RingNormalize + for<'x> From<<&'x R as Rem>::Output>, for<'x> &'x R: Rem,

Calculate the primitive part of the input polynomial, that is divide the polynomial by the GCD of its coefficents.

use polynomial_ring::{polynomial, Polynomial};
use num_traits::{One, Zero};
let mut f = polynomial![2i32, 4, -2, 6]; // 2+4x+2x^2+6x^3 ∈ Z[x]
f.primitive_part_mut();
assert_eq!(f, polynomial![1, 2, -1, 3]);// 1+2x+x^2+3x^3 ∈ Z[x]
let mut g = polynomial![polynomial![1i32, 1], polynomial![1, 2, 1], polynomial![3, 4, 1], polynomial![-1, -1]]; // (1+x)+(1+2x+x^2)y+(3+4x+x^2)y^2+(-1-x)y^3 ∈ Z[x][y]
g.primitive_part_mut();
assert_eq!(g, polynomial![polynomial![1], polynomial![1, 1], polynomial![3, 1], polynomial![-1]]); // 1+(1+x)y+(3+x)y^2-y^3 ∈ Z[x][y]

impl<K: Sized> Polynomial<K>

pub fn monic(&mut self)

where K: Clone + for<'x> DivAssign<&'x K>,

Make the polynomial monic, that is divide it by its leading coefficient.

use num::Rational64;
use polynomial_ring::Polynomial;
let mut p = Polynomial::new(vec![1, 2, 3].into_iter().map(|x| Rational64::from_integer(x)).collect());
p.monic();
let q = Polynomial::new(vec![(1, 3), (2, 3), (1, 1)].into_iter().map(|(n, d)| Rational64::new(n, d)).collect());
assert_eq!(p, q);

pub fn division(&mut self, other: &Self) -> Self

where K: Sized + Clone + Zero + for<'x> AddAssign<&'x K> + for<'x> SubAssign<&'x K> + for<'x> MulAssign<&'x K> + for<'x> DivAssign<&'x K>,

Polynomial division.

use num::Rational64;
use polynomial_ring::Polynomial;
let f = Polynomial::new(vec![3, 1, 4, 1, 5].into_iter().map(|x| Rational64::from_integer(x)).collect());
let g = Polynomial::new(vec![2, 7, 1].into_iter().map(|x| Rational64::from_integer(x)).collect());
let mut r = f.clone();
let q = r.division(&g);
assert_eq!(f, q * g + r);

pub fn square_free(&self) -> Self

where K: Sized + Clone + Zero + One + for<'x> AddAssign<&'x K> + for<'x> SubAssign<&'x K> + for<'x> MulAssign<&'x K> + for<'x> DivAssign<&'x K> + for<'x> From<<&'x K as Mul>::Output> + for<'x> From<<&'x K as Div>::Output>, for<'x> &'x K: Mul + Div,

Calculate the square-free decomposition.

use polynomial_ring::{Polynomial, polynomial};
use num::Rational64;
let f = polynomial![Rational64::from(1), Rational64::from(1)];
let g = polynomial![Rational64::from(1), Rational64::from(1), Rational64::from(1)];
let p = &f * &f * &f * &g * &g; // (x+1)^3(x^2+x+1)^2
assert_eq!(p.square_free(), &f * &g); // (x+1)(x^2+x+1)

Trait Implementations

impl<M> Add<&Polynomial<M>> for &Polynomial<M>

where M: Sized + Zero + for<'x> AddAssign<&'x M>, Polynomial<M>: Clone,

type Output = Polynomial<M>

The resulting type after applying the + operator.

fn add(self, rhs: &Polynomial<M>) -> Self::Output

Performs the + operation.

impl<M> Add<&Polynomial<M>> for Polynomial<M>

where M: Sized + Zero + for<'x> AddAssign<&'x M>,

type Output = Polynomial<M>

The resulting type after applying the + operator.

fn add(self, rhs: &Polynomial<M>) -> Self::Output

Performs the + operation.

impl<M> Add<Polynomial<M>> for &Polynomial<M>

where M: Sized + Zero + for<'x> AddAssign<&'x M>, Polynomial<M>: Clone,

type Output = Polynomial<M>

The resulting type after applying the + operator.

fn add(self, rhs: Polynomial<M>) -> Self::Output

Performs the + operation.

impl<M> Add for Polynomial<M>

where M: Sized + Zero + for<'x> AddAssign<&'x M>,

type Output = Polynomial<M>

The resulting type after applying the + operator.

fn add(self, rhs: Polynomial<M>) -> Self::Output

Performs the + operation.

impl<M> AddAssign<&Polynomial<M>> for Polynomial<M>

where M: Sized + Zero + for<'x> AddAssign<&'x M>,

fn add_assign(&mut self, other: &Self)

Performs the += operation.

impl<M> AddAssign for Polynomial<M>

where M: Sized + Zero + for<'x> AddAssign<&'x M>,

fn add_assign(&mut self, rhs: Polynomial<M>)

Performs the += operation.

impl<T: Clone> Clone for Polynomial<T>

fn clone(&self) -> Polynomial<T>

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<T: Debug> Debug for Polynomial<T>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<T: Default> Default for Polynomial<T>

fn default() -> Polynomial<T>

Returns the “default value” for a type.

impl<R> Display for Polynomial<R>

where R: PartialEq + Display + Zero + One,

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<K> Div<&Polynomial<K>> for Polynomial<K>

where K: Sized + Clone + Zero + for<'x> AddAssign<&'x K> + for<'x> SubAssign<&'x K> + for<'x> MulAssign<&'x K> + for<'x> DivAssign<&'x K>,

type Output = Polynomial<K>

The resulting type after applying the / operator.

fn div(self, rhs: &Polynomial<K>) -> Self::Output

Performs the / operation.

impl<R> Div<&R> for &Polynomial<R>

where R: Sized + for<'x> DivAssign<&'x R>, Polynomial<R>: Clone,

type Output = Polynomial<R>

The resulting type after applying the / operator.

fn div(self, rhs: &R) -> Self::Output

Performs the / operation.

impl<R> Div<&R> for Polynomial<R>

where R: Sized + for<'x> DivAssign<&'x R>,

type Output = Polynomial<R>

The resulting type after applying the / operator.

fn div(self, rhs: &R) -> Self::Output

Performs the / operation.

impl<K> Div<Polynomial<K>> for &Polynomial<K>

where K: Sized + Clone + Zero + for<'x> AddAssign<&'x K> + for<'x> SubAssign<&'x K> + for<'x> MulAssign<&'x K> + for<'x> DivAssign<&'x K>,

type Output = Polynomial<K>

The resulting type after applying the / operator.

fn div(self, rhs: Polynomial<K>) -> Self::Output

Performs the / operation.

impl<R> Div<R> for &Polynomial<R>

where R: Sized + for<'x> DivAssign<&'x R>, Polynomial<R>: Clone,

type Output = Polynomial<R>

The resulting type after applying the / operator.

fn div(self, rhs: R) -> Self::Output

Performs the / operation.

impl<R> Div<R> for Polynomial<R>

where R: Sized + for<'x> DivAssign<&'x R>,

type Output = Polynomial<R>

The resulting type after applying the / operator.

fn div(self, rhs: R) -> Self::Output

Performs the / operation.

impl<K> Div for &Polynomial<K>

where K: Sized + Clone + Zero + for<'x> AddAssign<&'x K> + for<'x> SubAssign<&'x K> + for<'x> MulAssign<&'x K> + for<'x> DivAssign<&'x K>,

type Output = Polynomial<K>

The resulting type after applying the / operator.

fn div(self, other: Self) -> Self::Output

Performs the / operation.

impl<K> Div for Polynomial<K>

where K: Sized + Clone + Zero + for<'x> AddAssign<&'x K> + for<'x> SubAssign<&'x K> + for<'x> MulAssign<&'x K> + for<'x> DivAssign<&'x K>,

type Output = Polynomial<K>

The resulting type after applying the / operator.

fn div(self, rhs: Polynomial<K>) -> Self::Output

Performs the / operation.

impl<K> DivAssign<&Polynomial<K>> for Polynomial<K>

where K: Sized + Clone + Zero + for<'x> AddAssign<&'x K> + for<'x> SubAssign<&'x K> + for<'x> MulAssign<&'x K> + for<'x> DivAssign<&'x K>,

fn div_assign(&mut self, rhs: &Polynomial<K>)

Performs the /= operation.

impl<R> DivAssign<&R> for Polynomial<R>

where R: Sized + for<'x> DivAssign<&'x R>,

fn div_assign(&mut self, alpha: &R)

Performs the /= operation.

impl<R> DivAssign<R> for Polynomial<R>

where R: Sized + for<'x> DivAssign<&'x R>,

fn div_assign(&mut self, rhs: R)

Performs the /= operation.

impl<K> DivAssign for Polynomial<K>

where K: Sized + Clone + Zero + for<'x> AddAssign<&'x K> + for<'x> SubAssign<&'x K> + for<'x> MulAssign<&'x K> + for<'x> DivAssign<&'x K>,

fn div_assign(&mut self, rhs: Polynomial<K>)

Performs the /= operation.

impl<R> Mul<&Polynomial<R>> for Polynomial<R>

where R: Sized + Clone + Zero + for<'x> AddAssign<&'x R> + for<'x> MulAssign<&'x R>,

type Output = Polynomial<R>

The resulting type after applying the * operator.

fn mul(self, rhs: &Polynomial<R>) -> Self::Output

Performs the * operation.

impl<R> Mul<&R> for &Polynomial<R>

where R: Sized + Zero + for<'x> MulAssign<&'x R>, Polynomial<R>: Clone,

type Output = Polynomial<R>

The resulting type after applying the * operator.

fn mul(self, rhs: &R) -> Self::Output

Performs the * operation.

impl<R> Mul<&R> for Polynomial<R>

where R: Sized + Zero + for<'x> MulAssign<&'x R>,

type Output = Polynomial<R>

The resulting type after applying the * operator.

fn mul(self, rhs: &R) -> Self::Output

Performs the * operation.

impl<R> Mul<Polynomial<R>> for &Polynomial<R>

where R: Sized + Clone + Zero + for<'x> AddAssign<&'x R> + for<'x> MulAssign<&'x R>,

type Output = Polynomial<R>

The resulting type after applying the * operator.

fn mul(self, rhs: Polynomial<R>) -> Self::Output

Performs the * operation.

impl<R> Mul<R> for &Polynomial<R>

where R: Sized + Zero + for<'x> MulAssign<&'x R>, Polynomial<R>: Clone,

type Output = Polynomial<R>

The resulting type after applying the * operator.

fn mul(self, rhs: R) -> Self::Output

Performs the * operation.

impl<R> Mul<R> for Polynomial<R>

where R: Sized + Zero + for<'x> MulAssign<&'x R>,

type Output = Polynomial<R>

The resulting type after applying the * operator.

fn mul(self, rhs: R) -> Self::Output

Performs the * operation.

impl<R> Mul for &Polynomial<R>

where R: Sized + Clone + Zero + for<'x> AddAssign<&'x R> + for<'x> MulAssign<&'x R>,

type Output = Polynomial<R>

The resulting type after applying the * operator.

fn mul(self, other: Self) -> Self::Output

Performs the * operation.

impl<R> Mul for Polynomial<R>

where R: Sized + Clone + Zero + for<'x> AddAssign<&'x R> + for<'x> MulAssign<&'x R>,

type Output = Polynomial<R>

The resulting type after applying the * operator.

fn mul(self, rhs: Polynomial<R>) -> Self::Output

Performs the * operation.

impl<R> MulAssign<&Polynomial<R>> for Polynomial<R>

where R: Sized + Clone + Zero + for<'x> AddAssign<&'x R> + for<'x> MulAssign<&'x R>,

fn mul_assign(&mut self, rhs: &Polynomial<R>)

Performs the *= operation.

impl<R> MulAssign<&R> for Polynomial<R>

where R: Sized + Zero + for<'x> MulAssign<&'x R>,

fn mul_assign(&mut self, alpha: &R)

Performs the *= operation.

impl<R> MulAssign<R> for Polynomial<R>

where R: Sized + Zero + for<'x> MulAssign<&'x R>,

fn mul_assign(&mut self, rhs: R)

Performs the *= operation.

impl<R> MulAssign for Polynomial<R>

where R: Sized + Clone + Zero + for<'x> AddAssign<&'x R> + for<'x> MulAssign<&'x R>,

fn mul_assign(&mut self, rhs: Polynomial<R>)

Performs the *= operation.

impl<G> Neg for &Polynomial<G>

where G: Sized + for<'x> From<<&'x G as Neg>::Output>, for<'x> &'x G: Neg,

type Output = Polynomial<G>

The resulting type after applying the - operator.

fn neg(self) -> Self::Output

Performs the unary - operation.

impl<G> Neg for Polynomial<G>

where G: Sized + Neg<Output = G>,

type Output = Polynomial<G>

The resulting type after applying the - operator.

fn neg(self) -> Self::Output

Performs the unary - operation.

impl<R> One for Polynomial<R>

where R: Sized + Clone + Zero + for<'x> AddAssign<&'x R> + One + for<'x> MulAssign<&'x R>,

fn one() -> Self

Returns the multiplicative identity element of Self, 1.

fn set_one(&mut self)

Sets self to the multiplicative identity element of Self, 1.

fn is_one(&self) -> bool

where Self: PartialEq,

Returns true if self is equal to the multiplicative identity.

impl<T: PartialEq> PartialEq for Polynomial<T>

fn eq(&self, other: &Polynomial<T>) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<R> Product for Polynomial<R>

where R: Sized + Clone + Zero + for<'x> AddAssign<&'x R> + One + for<'x> MulAssign<&'x R>,

fn product<I: Iterator<Item = Self>>(iter: I) -> Self

Takes an iterator and generates Self from the elements by multiplying the items.

impl<K> Rem<&Polynomial<K>> for &Polynomial<K>

where K: Sized + Clone + Zero + for<'x> AddAssign<&'x K> + for<'x> SubAssign<&'x K> + for<'x> MulAssign<&'x K> + for<'x> DivAssign<&'x K>, Polynomial<K>: Clone,

type Output = Polynomial<K>

The resulting type after applying the % operator.

fn rem(self, rhs: &Polynomial<K>) -> Self::Output

Performs the % operation.

impl<K> Rem<&Polynomial<K>> for Polynomial<K>

where K: Sized + Clone + Zero + for<'x> AddAssign<&'x K> + for<'x> SubAssign<&'x K> + for<'x> MulAssign<&'x K> + for<'x> DivAssign<&'x K>,

type Output = Polynomial<K>

The resulting type after applying the % operator.

fn rem(self, rhs: &Polynomial<K>) -> Self::Output

Performs the % operation.

impl<K> Rem<Polynomial<K>> for &Polynomial<K>

where K: Sized + Clone + Zero + for<'x> AddAssign<&'x K> + for<'x> SubAssign<&'x K> + for<'x> MulAssign<&'x K> + for<'x> DivAssign<&'x K>, Polynomial<K>: Clone,

type Output = Polynomial<K>

The resulting type after applying the % operator.

fn rem(self, rhs: Polynomial<K>) -> Self::Output

Performs the % operation.

impl<K> Rem for Polynomial<K>

where K: Sized + Clone + Zero + for<'x> AddAssign<&'x K> + for<'x> SubAssign<&'x K> + for<'x> MulAssign<&'x K> + for<'x> DivAssign<&'x K>,

type Output = Polynomial<K>

The resulting type after applying the % operator.

fn rem(self, rhs: Polynomial<K>) -> Self::Output

Performs the % operation.

impl<K> RemAssign<&Polynomial<K>> for Polynomial<K>

where K: Sized + Clone + Zero + for<'x> AddAssign<&'x K> + for<'x> SubAssign<&'x K> + for<'x> MulAssign<&'x K> + for<'x> DivAssign<&'x K>,

fn rem_assign(&mut self, other: &Self)

Performs the %= operation.

impl<K> RemAssign for Polynomial<K>

where K: Sized + Clone + Zero + for<'x> AddAssign<&'x K> + for<'x> SubAssign<&'x K> + for<'x> MulAssign<&'x K> + for<'x> DivAssign<&'x K>,

fn rem_assign(&mut self, rhs: Polynomial<K>)

Performs the %= operation.

impl<K> RingNormalize for Polynomial<K>

where K: Sized + Clone + Zero + One + for<'x> AddAssign<&'x K> + for<'x> MulAssign<&'x K> + for<'x> DivAssign<&'x K>,

fn leading_unit(&self) -> Self

fn normalize_mut(&mut self)

fn into_normalize(self) -> Self

where Self: Sized,

fn normalize(&self) -> Self

where Self: Clone,

fn is_similar(&self, other: &Self) -> bool

where Self: Clone + Eq,

impl<G> Sub<&Polynomial<G>> for &Polynomial<G>

where G: Sized + Zero + for<'x> SubAssign<&'x G>, Polynomial<G>: Clone,

type Output = Polynomial<G>

The resulting type after applying the - operator.

fn sub(self, rhs: &Polynomial<G>) -> Self::Output

Performs the - operation.

impl<G> Sub<&Polynomial<G>> for Polynomial<G>

where G: Sized + Zero + for<'x> SubAssign<&'x G>,

type Output = Polynomial<G>

The resulting type after applying the - operator.

fn sub(self, rhs: &Polynomial<G>) -> Self::Output

Performs the - operation.

impl<G> Sub<Polynomial<G>> for &Polynomial<G>

where G: Sized + Zero + for<'x> SubAssign<&'x G>, Polynomial<G>: Clone,

type Output = Polynomial<G>

The resulting type after applying the - operator.

fn sub(self, rhs: Polynomial<G>) -> Self::Output

Performs the - operation.

impl<G> Sub for Polynomial<G>

where G: Sized + Zero + for<'x> SubAssign<&'x G>,

type Output = Polynomial<G>

The resulting type after applying the - operator.

fn sub(self, rhs: Polynomial<G>) -> Self::Output

Performs the - operation.

impl<G> SubAssign<&Polynomial<G>> for Polynomial<G>

where G: Sized + Zero + for<'x> SubAssign<&'x G>,

fn sub_assign(&mut self, other: &Self)

Performs the -= operation.

impl<G> SubAssign for Polynomial<G>

where G: Sized + Zero + for<'x> SubAssign<&'x G>,

fn sub_assign(&mut self, rhs: Polynomial<G>)

Performs the -= operation.

impl<M> Sum for Polynomial<M>

where M: Sized + Zero + for<'x> AddAssign<&'x M>,

fn sum<I: Iterator<Item = Self>>(iter: I) -> Self

Takes an iterator and generates Self from the elements by “summing up” the items.

impl<M> Zero for Polynomial<M>

where M: Sized + Zero + for<'x> AddAssign<&'x M>,

fn zero() -> Self

Returns the additive identity element of Self, 0.

fn is_zero(&self) -> bool

Returns true if self is equal to the additive identity.

fn set_zero(&mut self)

Sets self to the additive identity element of Self, 0.

impl<T: Eq> Eq for Polynomial<T>

impl<T> StructuralPartialEq for Polynomial<T>