Trait PolyRing 

pub trait PolyRing: RingExtension {
    type TermsIterator<'a>: Iterator<Item = (&'a El<Self::BaseRing>, usize)>
       where Self: 'a;

    // Required methods
    fn indeterminate(&self) -> Self::Element;
    fn terms<'a>(&'a self, f: &'a Self::Element) -> Self::TermsIterator<'a>;
    fn coefficient_at<'a>(
        &'a self,
        f: &'a Self::Element,
        i: usize,
    ) -> &'a El<Self::BaseRing>;
    fn degree(&self, f: &Self::Element) -> Option<usize>;
    fn div_rem_monic(
        &self,
        lhs: Self::Element,
        rhs: &Self::Element,
    ) -> (Self::Element, Self::Element);

    // Provided methods
    fn add_assign_from_terms<I>(&self, lhs: &mut Self::Element, rhs: I)
       where I: IntoIterator<Item = (El<Self::BaseRing>, usize)> { ... }
    fn mul_assign_monomial(&self, lhs: &mut Self::Element, rhs_power: usize) { ... }
    fn truncate_monomials(
        &self,
        lhs: &mut Self::Element,
        truncated_at_inclusive: usize,
    ) { ... }
    fn map_terms<P, H>(
        &self,
        from: &P,
        el: &P::Element,
        hom: H,
    ) -> Self::Element
       where P: ?Sized + PolyRing,
             H: Homomorphism<<P::BaseRing as RingStore>::Type, <Self::BaseRing as RingStore>::Type> { ... }
    fn balance_poly(&self, f: &mut Self::Element) -> Option<El<Self::BaseRing>>
       where <Self::BaseRing as RingStore>::Type: DivisibilityRing { ... }
    fn evaluate<R, H>(
        &self,
        f: &Self::Element,
        value: &R::Element,
        hom: H,
    ) -> R::Element
       where R: ?Sized + RingBase,
             H: Homomorphism<<Self::BaseRing as RingStore>::Type, R> { ... }
}

Trait for all rings that represent the polynomial ring R[X] with any base ring R.

Currently, the two implementations of this type of ring are dense_poly::DensePolyRing and sparse_poly::SparsePolyRing.

Required Associated Types

type TermsIterator<'a>: Iterator<Item = (&'a El<Self::BaseRing>, usize)> where Self: 'a

Type of the iterator over all non-zero terms of a polynomial in this ring, as returned by PolyRing::terms().

Required Methods

fn indeterminate(&self) -> Self::Element

Returns the indeterminate X generating this polynomial ring.

fn terms<'a>(&'a self, f: &'a Self::Element) -> Self::TermsIterator<'a>

Returns all the nonzero terms of the given polynomial.

If the base ring is only approximate, it is valid to return “zero” terms, whatever that actually means.

fn coefficient_at<'a>( &'a self, f: &'a Self::Element, i: usize, ) -> &'a El<Self::BaseRing>

Returns the coefficient of f that corresponds to the monomial X^i.

fn degree(&self, f: &Self::Element) -> Option<usize>

Returns the degree of the polynomial f, i.e. the value d such that f can be written as f(X) = a0 + a1 * X + a2 * X^2 + ... + ad * X^d. Returns None if f is zero.

fn div_rem_monic( &self, lhs: Self::Element, rhs: &Self::Element, ) -> (Self::Element, Self::Element)

Compute the euclidean division by a monic polynomial rhs.

Concretely, if rhs is a monic polynomial (polynomial with highest coefficient equal to 1), then there exist unique q, r such that lhs = rhs * q + r and deg(r) < deg(rhs). These are returned. This function panics if rhs is not monic.

Provided Methods

fn add_assign_from_terms<I>(&self, lhs: &mut Self::Element, rhs: I)

where I: IntoIterator<Item = (El<Self::BaseRing>, usize)>,

Adds the given terms to the given polynomial.

fn mul_assign_monomial(&self, lhs: &mut Self::Element, rhs_power: usize)

Multiplies the given polynomial with X^rhs_power.

fn truncate_monomials( &self, lhs: &mut Self::Element, truncated_at_inclusive: usize, )

Truncates the monomials of the given polynomial from the given position on, i.e. computes the remainder of the polynomial division of lhs by X^truncated_at_inclusive.

fn map_terms<P, H>(&self, from: &P, el: &P::Element, hom: H) -> Self::Element

where P: ?Sized + PolyRing, H: Homomorphism<<P::BaseRing as RingStore>::Type, <Self::BaseRing as RingStore>::Type>,

Computes the polynomial whose coefficients are the images of the coefficients of el under the given homomorphism.

This is used to implement PolyRingStore::lifted_hom().

fn balance_poly(&self, f: &mut Self::Element) -> Option<El<Self::BaseRing>>

where <Self::BaseRing as RingStore>::Type: DivisibilityRing,

Possibly divides all coefficients of the polynomial by a common factor, in order to make them “smaller”.

In cases where we mainly care about polynomials up to scaling by non-zero divisors of the base ring, balancing intermediate polynomials can improve performance.

For more details on balancing, see DivisibilityRing::balance_factor().

fn evaluate<R, H>( &self, f: &Self::Element, value: &R::Element, hom: H, ) -> R::Element

where R: ?Sized + RingBase, H: Homomorphism<<Self::BaseRing as RingStore>::Type, R>,

Evaluates the given polynomial at the given values.

Example

let ring = dense_poly::DensePolyRing::new(StaticRing::<i32>::RING, "X");
let x = ring.indeterminate();
let poly = ring.add(ring.clone_el(&x), ring.pow(x, 2));
assert_eq!(12, ring.evaluate(&poly, &3, &StaticRing::<i32>::RING.identity()));

Dyn Compatibility

This trait is not dyn compatible.

In older versions of Rust, dyn compatibility was called "object safety", so this trait is not object safe.

Implementors

impl<R> PolyRing for SparsePolyRingBase<R>

where R: RingStore,

type TermsIterator<'a> = TermIterator<'a, R> where Self: 'a

impl<R, A: Allocator + Clone, C: ConvolutionAlgorithm<R::Type>> PolyRing for DensePolyRingBase<R, A, C>

where R: RingStore,

type TermsIterator<'a> = TermIterator<'a, R> where Self: 'a