Struct rustnomial::SparsePolynomial

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

This version of Polynomial is intended for use for polynomials of large degree, but with a very small number of internal terms. However, it is significantly slower than Polynomial in the case where the number of non-zero terms is 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> SparsePolynomial<N>

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

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.

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

Performs the + operation.

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

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

Performs the += operation.

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

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

Returns a copy of the value.

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

Performs copy-assignment from source.

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

pub 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>, 

pub 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, 

pub 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.

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

Performs the / operation.

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

pub 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>, 

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

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

pub 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)]);

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

Adds the term with given coefficient and degree to self.

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

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

Performs the conversion.

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

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

Performs the conversion.

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

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

Performs the conversion.

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

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

Performs the conversion.

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

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

Performs the conversion.

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

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

Performs the conversion.

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

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

Performs the conversion.

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

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

Performs the conversion.

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

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

Performs the conversion.

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

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

Performs the conversion.

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

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

Performs the conversion.

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

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

Performs the conversion.

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

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

Performs the conversion.

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

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

Performs the conversion.

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

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

Performs the conversion.

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

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

Performs the conversion.

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

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

Performs the conversion.

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

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

Performs the conversion.

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

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

Performs the conversion.

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

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

Performs the conversion.

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

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

Performs the conversion.

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

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

Performs the conversion.

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

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

Performs the conversion.

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

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

Performs the conversion.

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

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

Performs the conversion.

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

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

Performs the conversion.

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

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

Performs the conversion.

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

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

Performs the conversion.

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

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

Performs the conversion.

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

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

Performs the conversion.

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

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

Performs the conversion.

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

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

Performs the conversion.

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

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

Performs the conversion.

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

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

Performs the conversion.

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

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

Performs the conversion.

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

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

Performs the conversion.

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

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

Performs the conversion.

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

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

Performs the conversion.

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

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

Performs the conversion.

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

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

Performs the conversion.

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

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

Performs the conversion.

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

pub 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.

pub 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, 

pub 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, 

pub 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.

pub 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.

pub 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.

pub 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, 

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

Performs the *= operation.

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

pub 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, 

pub 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, 

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

Adds 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.

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

Subtracts 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.

pub fn neg(self) -> SparsePolynomial<N>

Performs the unary - operation.

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

pub 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);

#[must_use]pub 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, 

type Output = SparsePolynomial<N>

The resulting type after applying the % operator.

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

Returns the remainder of dividing self by _rhs.

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, 

pub 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.

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

Performs the << operation.

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

pub 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.

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

Performs the >> operation.

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

pub fn shr_assign(&mut self, _rhs: i32)

Performs the >>= operation.

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

pub fn len(&self) -> usize

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

Returns the term with the given degree from SizedPolynomial. 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.

pub 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());

pub 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.term_iter().next().is_none());
assert!(zero.terms.is_empty());

pub 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());

pub fn term_iter(&self) -> TermIterator<'_, N> where
    Self: Sized, 

Returns an iterator for the Polynomial, yielding the coefficient and degree of each non-zero term, in descending degree order.

pub fn is_zero(&self) -> bool

Returns true if all terms 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.

pub 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.

pub 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, 

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

Performs the -= operation.