Struct rustnomial::SparsePolynomial

pub struct SparsePolynomial<N> {
    pub terms: BTreeMap<usize, N>,
}

A type which stores the terms of a polynomial in a map. It is intended to store the terms of polynomials where the degree is significantly larger than the number of non-zero terms. Operations are significantly slower than with Polynomial if the number of non-zero terms is very close to the degree.

Fields

terms: BTreeMap<usize, N>

Implementations

impl SparsePolynomial<f64>

pub fn roots(self) -> Roots<f64>

Return the roots of the SparsePolynomial.

Example

use rustnomial::{SparsePolynomial, Roots, SizedPolynomial};
let zero = SparsePolynomial::<f64>::zero();
assert_eq!(Roots::InfiniteRoots, zero.roots());
let constant = SparsePolynomial::from(vec![1.]);
assert_eq!(Roots::NoRoots, constant.roots());
let monomial = SparsePolynomial::from(vec![1.0, 0.,]);
assert_eq!(Roots::ManyRealRoots(vec![0.]), monomial.roots());
let binomial = SparsePolynomial::from(vec![1.0, 2.0]);
assert_eq!(Roots::ManyRealRoots(vec![-2.0]), binomial.roots());
let trinomial = SparsePolynomial::from(vec![1.0, 4.0, 4.0]);
assert_eq!(Roots::ManyRealRoots(vec![-2.0, -2.0]), trinomial.roots());
let quadnomial = SparsePolynomial::from(vec![1.0, 6.0, 12.0, 8.0]);
assert_eq!(Roots::ManyRealRoots(vec![-2.0, -2.0, -2.0]), quadnomial.roots());

impl<N: Copy> SparsePolynomial<N>

pub fn new(terms: BTreeMap<usize, N>) -> SparsePolynomial<N>

impl<N: Copy + Zero> SparsePolynomial<N>

pub fn ordered_term_iter(&self) -> impl Iterator<Item = (N, usize)> + '_

impl<N> SparsePolynomial<N> where
    N: Mul<Output = N> + AddAssign + Copy + Zero + One, 

pub fn borrow_mul(&self, rhs: &SparsePolynomial<N>) -> SparsePolynomial<N>

pub fn pow(&self, exp: usize) -> SparsePolynomial<N>

Raises the SparsePolynomial to the power of exp, using exponentiation by squaring.

Example

use rustnomial::SparsePolynomial;
let polynomial = SparsePolynomial::from(vec![1.0, 2.0]);
let polynomial_sqr = polynomial.pow(2);
let polynomial_cub = polynomial.pow(3);
assert_eq!(polynomial.clone() * polynomial.clone(), polynomial_sqr);
assert_eq!(polynomial_sqr.clone() * polynomial.clone(), polynomial_cub);

impl<N> SparsePolynomial<N> where
    N: Copy + Zero + Neg<Output = N> + Sub<Output = N> + SubAssign + Mul<Output = N> + Div<Output = N> + AddAssign, 

pub fn div_mod(
    &self,
    rhs: &SparsePolynomial<N>
) -> (SparsePolynomial<N>, SparsePolynomial<N>)

Divides self by the given SparsePolynomial, and returns the quotient and remainder.

Example

use rustnomial::SparsePolynomial;
let polynomial = SparsePolynomial::from(vec![1.0, 2.0]);

Trait Implementations

impl<N> Add<SparsePolynomial<N>> for SparsePolynomial<N> where
    N: Copy + AddAssign, 

type Output = SparsePolynomial<N>

The resulting type after applying the + operator.

fn add(self, rhs: SparsePolynomial<N>) -> SparsePolynomial<N>

Performs the + operation.

impl<N: Copy + AddAssign> AddAssign<SparsePolynomial<N>> for SparsePolynomial<N>

fn add_assign(&mut self, rhs: SparsePolynomial<N>)

Performs the += operation.

impl<N: Clone> Clone for SparsePolynomial<N>

fn clone(&self) -> SparsePolynomial<N>

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<N: Debug> Debug for SparsePolynomial<N>

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

Formats the value using the given formatter.

impl<N> Derivable<N> for SparsePolynomial<N> where
    N: Zero + TryFromUsizeExact + Copy + Mul<Output = N>, 

fn derivative(&self) -> SparsePolynomial<N>

Returns the derivative of the SparsePolynomial.

Example

use rustnomial::{SparsePolynomial, Derivable};
let polynomial = SparsePolynomial::from(vec![4, 1, 5]);
assert_eq!(SparsePolynomial::from(vec![8, 1]), polynomial.derivative());

Errors

Will panic if a term has a degree which does not have a lossless representation in N.

impl<N> Display for SparsePolynomial<N> where
    N: Zero + One + IsPositive + PartialEq + Abs + Copy + IsNegativeOne + Display, 

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

Formats the value using the given formatter.

impl<N> Div<N> for SparsePolynomial<N> where
    N: Copy + Div<Output = N>, 

type Output = SparsePolynomial<N>

The resulting type after applying the / operator.

fn div(self, rhs: N) -> SparsePolynomial<N>

Performs the / operation.

impl<N> DivAssign<N> for SparsePolynomial<N> where
    N: Copy + DivAssign, 

fn div_assign(&mut self, rhs: N)

Performs the /= operation.

impl<N> Evaluable<N> for SparsePolynomial<N> where
    N: Zero + PowUsize + Copy + AddAssign + Mul<Output = N>, 

fn eval(&self, point: N) -> N

Evaluates self at point, and returns the result.

impl<N> FreeSizePolynomial<N> for SparsePolynomial<N> where
    N: Zero + Copy + AddAssign, 

fn from_terms(terms: &[(N, usize)]) -> Self

Returns a SparsePolynomial with the corresponding terms.

Arguments

• terms - A slice of (coefficient, degree) pairs.

Example

use rustnomial::{SparsePolynomial, FreeSizePolynomial};
// Corresponds to 1.0x^2 + 4.0x + 4.0
let polynomial = SparsePolynomial::from_terms(&[(1.0, 2), (4.0, 1), (4.0, 1)]);

fn add_term(&mut self, coeff: N, degree: usize)

Adds the term with given coefficient coeff and degree degree to self.

impl From<SparsePolynomial<f32>> for SparsePolynomial<f64>

fn from(item: SparsePolynomial<f32>) -> Self

Performs the conversion.

impl From<SparsePolynomial<i16>> for SparsePolynomial<i32>

fn from(item: SparsePolynomial<i16>) -> Self

Performs the conversion.

impl From<SparsePolynomial<i16>> for SparsePolynomial<i64>

fn from(item: SparsePolynomial<i16>) -> Self

Performs the conversion.

impl From<SparsePolynomial<i16>> for SparsePolynomial<i128>

fn from(item: SparsePolynomial<i16>) -> Self

Performs the conversion.

impl From<SparsePolynomial<i16>> for SparsePolynomial<f32>

fn from(item: SparsePolynomial<i16>) -> Self

Performs the conversion.

impl From<SparsePolynomial<i16>> for SparsePolynomial<f64>

fn from(item: SparsePolynomial<i16>) -> Self

Performs the conversion.

impl From<SparsePolynomial<i32>> for SparsePolynomial<i64>

fn from(item: SparsePolynomial<i32>) -> Self

Performs the conversion.

impl From<SparsePolynomial<i32>> for SparsePolynomial<i128>

fn from(item: SparsePolynomial<i32>) -> Self

Performs the conversion.

impl From<SparsePolynomial<i32>> for SparsePolynomial<f64>

fn from(item: SparsePolynomial<i32>) -> Self

Performs the conversion.

impl From<SparsePolynomial<i64>> for SparsePolynomial<i128>

fn from(item: SparsePolynomial<i64>) -> Self

Performs the conversion.

impl From<SparsePolynomial<i8>> for SparsePolynomial<i16>

fn from(item: SparsePolynomial<i8>) -> Self

Performs the conversion.

impl From<SparsePolynomial<i8>> for SparsePolynomial<i32>

fn from(item: SparsePolynomial<i8>) -> Self

Performs the conversion.

impl From<SparsePolynomial<i8>> for SparsePolynomial<i64>

fn from(item: SparsePolynomial<i8>) -> Self

Performs the conversion.

impl From<SparsePolynomial<i8>> for SparsePolynomial<i128>

fn from(item: SparsePolynomial<i8>) -> Self

Performs the conversion.

impl From<SparsePolynomial<i8>> for SparsePolynomial<f32>

fn from(item: SparsePolynomial<i8>) -> Self

Performs the conversion.

impl From<SparsePolynomial<i8>> for SparsePolynomial<f64>

fn from(item: SparsePolynomial<i8>) -> Self

Performs the conversion.

impl From<SparsePolynomial<u16>> for SparsePolynomial<u32>

fn from(item: SparsePolynomial<u16>) -> Self

Performs the conversion.

impl From<SparsePolynomial<u16>> for SparsePolynomial<u64>

fn from(item: SparsePolynomial<u16>) -> Self

Performs the conversion.

impl From<SparsePolynomial<u16>> for SparsePolynomial<u128>

fn from(item: SparsePolynomial<u16>) -> Self

Performs the conversion.

impl From<SparsePolynomial<u16>> for SparsePolynomial<i32>

fn from(item: SparsePolynomial<u16>) -> Self

Performs the conversion.

impl From<SparsePolynomial<u16>> for SparsePolynomial<i64>

fn from(item: SparsePolynomial<u16>) -> Self

Performs the conversion.

impl From<SparsePolynomial<u16>> for SparsePolynomial<i128>

fn from(item: SparsePolynomial<u16>) -> Self

Performs the conversion.

impl From<SparsePolynomial<u16>> for SparsePolynomial<f32>

fn from(item: SparsePolynomial<u16>) -> Self

Performs the conversion.

impl From<SparsePolynomial<u16>> for SparsePolynomial<f64>

fn from(item: SparsePolynomial<u16>) -> Self

Performs the conversion.

impl From<SparsePolynomial<u32>> for SparsePolynomial<u64>

fn from(item: SparsePolynomial<u32>) -> Self

Performs the conversion.

impl From<SparsePolynomial<u32>> for SparsePolynomial<u128>

fn from(item: SparsePolynomial<u32>) -> Self

Performs the conversion.

impl From<SparsePolynomial<u32>> for SparsePolynomial<i64>

fn from(item: SparsePolynomial<u32>) -> Self

Performs the conversion.

impl From<SparsePolynomial<u32>> for SparsePolynomial<i128>

fn from(item: SparsePolynomial<u32>) -> Self

Performs the conversion.

impl From<SparsePolynomial<u32>> for SparsePolynomial<f64>

fn from(item: SparsePolynomial<u32>) -> Self

Performs the conversion.

impl From<SparsePolynomial<u64>> for SparsePolynomial<u128>

fn from(item: SparsePolynomial<u64>) -> Self

Performs the conversion.

impl From<SparsePolynomial<u64>> for SparsePolynomial<i128>

fn from(item: SparsePolynomial<u64>) -> Self

Performs the conversion.

impl From<SparsePolynomial<u8>> for SparsePolynomial<u16>

fn from(item: SparsePolynomial<u8>) -> Self

Performs the conversion.

impl From<SparsePolynomial<u8>> for SparsePolynomial<u32>

fn from(item: SparsePolynomial<u8>) -> Self

Performs the conversion.

impl From<SparsePolynomial<u8>> for SparsePolynomial<u64>

fn from(item: SparsePolynomial<u8>) -> Self

Performs the conversion.

impl From<SparsePolynomial<u8>> for SparsePolynomial<u128>

fn from(item: SparsePolynomial<u8>) -> Self

Performs the conversion.

impl From<SparsePolynomial<u8>> for SparsePolynomial<i16>

fn from(item: SparsePolynomial<u8>) -> Self

Performs the conversion.

impl From<SparsePolynomial<u8>> for SparsePolynomial<i32>

fn from(item: SparsePolynomial<u8>) -> Self

Performs the conversion.

impl From<SparsePolynomial<u8>> for SparsePolynomial<i64>

fn from(item: SparsePolynomial<u8>) -> Self

Performs the conversion.

impl From<SparsePolynomial<u8>> for SparsePolynomial<i128>

fn from(item: SparsePolynomial<u8>) -> Self

Performs the conversion.

impl From<SparsePolynomial<u8>> for SparsePolynomial<f32>

fn from(item: SparsePolynomial<u8>) -> Self

Performs the conversion.

impl From<SparsePolynomial<u8>> for SparsePolynomial<f64>

fn from(item: SparsePolynomial<u8>) -> Self

Performs the conversion.

impl<N> From<Vec<N, Global>> for SparsePolynomial<N> where
    N: Copy + Zero, 

fn from(term_vec: Vec<N>) -> Self

Returns a SparsePolynomial with the corresponding terms, in order of ax^n + bx^(n-1) + … + cx + d

Arguments

• term_vec - A vector of constants, in decreasing order of degree.

Example

use rustnomial::SparsePolynomial;
// Corresponds to 1.0x^2 + 4.0x + 4.0
let polynomial = SparsePolynomial::from(vec![1.0, 4.0, 4.0]);

impl<N> FromStr for SparsePolynomial<N> where
    N: Zero + One + Copy + SubAssign + AddAssign + FromStr + CanNegate, 

type Err = PolynomialFromStringError

The associated error which can be returned from parsing.

fn from_str(s: &str) -> Result<Self, Self::Err>

Parses a string s to return a value of this type.

impl<N> Integrable<N, SparsePolynomial<N>> for Monomial<N> where
    N: Zero + Copy + Mul<Output = N> + AddAssign + PowUsize + Div<Output = N> + TryFromUsizeExact, 

fn integral(&self) -> Integral<N, SparsePolynomial<N>>

Returns the integral of the Monomial.

Example

use rustnomial::{Monomial, SparsePolynomial, Integrable, FreeSizePolynomial};
let monomial = Monomial::new(3.0, 2);
let integral = monomial.integral();
assert_eq!(&SparsePolynomial::from_terms(&[(1.0, 3)]), integral.inner());
assert_eq!(1., integral.eval(0., 1.));

impl<N> Integrable<N, SparsePolynomial<N>> for SparsePolynomial<N> where
    N: PartialEq + Zero + Copy + Div<Output = N> + Mul<Output = N> + PowUsize + AddAssign + TryFromUsizeExact, 

fn integral(&self) -> Integral<N, SparsePolynomial<N>>

Returns the integral of the Polynomial.

Example

use rustnomial::{SparsePolynomial, Integrable};
let polynomial = SparsePolynomial::from(vec![1.0, 2.0, 5.0]);
let integral = polynomial.integral();
assert_eq!(&SparsePolynomial::from(vec![1.0/3.0, 1.0, 5.0, 0.0]), integral.inner());

Errors

Will panic if a term has a degree, which when incremented by one, does not have a lossless representation in N.

impl<N> Mul<&'_ SparsePolynomial<N>> for SparsePolynomial<N> where
    N: Mul<Output = N> + AddAssign + Copy + Zero, 

type Output = SparsePolynomial<N>

The resulting type after applying the * operator.

fn mul(self, rhs: &SparsePolynomial<N>) -> SparsePolynomial<N>

Performs the * operation.

impl<N: Copy + Mul<Output = N>> Mul<N> for SparsePolynomial<N>

type Output = SparsePolynomial<N>

The resulting type after applying the * operator.

fn mul(self, rhs: N) -> SparsePolynomial<N>

Performs the * operation.

impl<N> Mul<SparsePolynomial<N>> for SparsePolynomial<N> where
    N: Mul<Output = N> + AddAssign + Copy + Zero, 

type Output = SparsePolynomial<N>

The resulting type after applying the * operator.

fn mul(self, rhs: SparsePolynomial<N>) -> SparsePolynomial<N>

Performs the * operation.

impl<N> MulAssign<&'_ SparsePolynomial<N>> for SparsePolynomial<N> where
    N: Mul<Output = N> + AddAssign + Copy + Zero, 

fn mul_assign(&mut self, rhs: &SparsePolynomial<N>)

Performs the *= operation.

impl<N: Copy + MulAssign> MulAssign<N> for SparsePolynomial<N>

fn mul_assign(&mut self, rhs: N)

Performs the *= operation.

impl<N> MulAssign<SparsePolynomial<N>> for SparsePolynomial<N> where
    N: Mul<Output = N> + AddAssign + Copy + Zero, 

fn mul_assign(&mut self, rhs: SparsePolynomial<N>)

Performs the *= operation.

impl<N> MutablePolynomial<N> for SparsePolynomial<N> where
    N: Zero + Copy + AddAssign + SubAssign + CanNegate, 

fn try_add_term(&mut self, coeff: N, degree: usize) -> Result<(), TryAddError>

Tries to add the term with given coefficient and degree to self, returning an error if the particular term can not be added to self without violating constraints.

fn try_sub_term(&mut self, coeff: N, degree: usize) -> Result<(), TryAddError>

Tries to subtract the term with given coefficient and degree from self, returning an error if the particular term can not be subtracted from self without violating constraints.

impl<N> Neg for SparsePolynomial<N> where
    N: Zero + Copy + Neg<Output = N>, 

type Output = SparsePolynomial<N>

The resulting type after applying the - operator.

fn neg(self) -> SparsePolynomial<N>

Performs the unary - operation.

impl<N> PartialEq<SparsePolynomial<N>> for SparsePolynomial<N> where
    N: Zero + PartialEq + Copy, 

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

Returns true if self has the same terms as other.

Example

use rustnomial::SparsePolynomial;
let a = SparsePolynomial::from(vec![1.0, 2.0]);
let b = SparsePolynomial::from(vec![2.0, 2.0]);
let c = SparsePolynomial::from(vec![1.0, 0.0]);
assert_ne!(a, b);
assert_ne!(a, c);
assert_eq!(a, b - c);

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

This method tests for !=.

impl<N> Rem<SparsePolynomial<N>> for SparsePolynomial<N> where
    N: Copy + Zero + Neg<Output = N> + Sub<Output = N> + SubAssign + Mul<Output = N> + Div<Output = N> + AddAssign, 

fn rem(self, rhs: SparsePolynomial<N>) -> SparsePolynomial<N>

Returns the remainder of dividing self by rhs.

type Output = SparsePolynomial<N>

The resulting type after applying the % operator.

impl<N> RemAssign<SparsePolynomial<N>> for SparsePolynomial<N> where
    N: Copy + Zero + Neg<Output = N> + Sub<Output = N> + SubAssign + Mul<Output = N> + Div<Output = N> + AddAssign, 

fn rem_assign(&mut self, rhs: SparsePolynomial<N>)

Assign the remainder of dividing self by rhs to self.

impl<N: Copy> Shl<i32> for SparsePolynomial<N>

type Output = SparsePolynomial<N>

The resulting type after applying the << operator.

fn shl(self, rhs: i32) -> SparsePolynomial<N>

Performs the << operation.

impl<N: Copy> ShlAssign<i32> for SparsePolynomial<N>

fn shl_assign(&mut self, rhs: i32)

Performs the <<= operation.

impl<N: Copy> Shr<i32> for SparsePolynomial<N>

type Output = SparsePolynomial<N>

The resulting type after applying the >> operator.

fn shr(self, rhs: i32) -> SparsePolynomial<N>

Performs the >> operation.

impl<N: Copy> ShrAssign<i32> for SparsePolynomial<N>

fn shr_assign(&mut self, rhs: i32)

Performs the >>= operation.

impl<N: Zero + Copy> SizedPolynomial<N> for SparsePolynomial<N>

fn degree(&self) -> Degree

Returns the degree of the SparsePolynomial it is called on, corresponding to the largest non-zero term.

Example

use rustnomial::{SizedPolynomial, SparsePolynomial, Degree};
let polynomial = SparsePolynomial::from(vec![1.0, 4.0, 4.0]);
assert_eq!(Degree::Num(2), polynomial.degree());

fn zero() -> SparsePolynomial<N>

Returns a SparsePolynomial with no terms.

Example

use rustnomial::{SizedPolynomial, SparsePolynomial};
let zero = SparsePolynomial::<i32>::zero();
assert!(zero.is_zero());
assert!(zero.ordered_term_iter().next().is_none());
assert!(zero.terms.is_empty());

fn set_to_zero(&mut self)

Sets self to zero.

Example

use rustnomial::{SparsePolynomial, SizedPolynomial};
let mut non_zero = SparsePolynomial::from(vec![0, 1]);
assert!(!non_zero.is_zero());
non_zero.set_to_zero();
assert!(non_zero.is_zero());

fn term_with_degree(&self, degree: usize) -> Term<N>

Returns the term with the given degree from self. If the term degree is larger than the actual degree, ZeroTerm will be returned. However, terms which are zero will also be returned as ZeroTerm, so this does not indicate that the final term has been reached.

fn terms_as_vec(&self) -> Vec<(N, usize)>

Returns a Vec containing all of the terms of self, where each item is the coefficient and degree of each non-zero term, in order of descending degree.

fn is_zero(&self) -> bool

Returns true if all terms of self are zero, and false if a non-zero term exists.

impl<N> Sub<Polynomial<N>> for SparsePolynomial<N> where
    N: Zero + Copy + Sub<Output = N> + SubAssign + Neg<Output = N>, 

type Output = SparsePolynomial<N>

The resulting type after applying the - operator.

fn sub(self, rhs: Polynomial<N>) -> SparsePolynomial<N>

Performs the - operation.

impl<N> Sub<SparsePolynomial<N>> for SparsePolynomial<N> where
    N: Zero + Copy + Sub<Output = N> + SubAssign + Neg<Output = N>, 

type Output = SparsePolynomial<N>

The resulting type after applying the - operator.

fn sub(self, rhs: SparsePolynomial<N>) -> SparsePolynomial<N>

Performs the - operation.

impl<N> SubAssign<SparsePolynomial<N>> for SparsePolynomial<N> where
    N: Neg<Output = N> + Sub<Output = N> + SubAssign + Copy, 

fn sub_assign(&mut self, rhs: SparsePolynomial<N>)

Performs the -= operation.