Struct EvaluationDomain

pub struct EvaluationDomain<F: Field> { /* private fields */ }

A domain that univariate polynomials may be evaluated on.

An evaluation domain of size d + 1 along with polynomial values on that domain are sufficient to reconstruct a degree <= d. This struct supports Barycentric extrapolation.

A domain may optionally include a Karatsuba “infinity” point, “evaluating” a polynomial at which results in taking the coefficient at the highest degree term. This point requires special treatment but sometimes unlocks optimization opportunities. The “Evaluation” section of the Wikipedia article on Toom-Cook multiplication gives a great explanation of the concept.

Implementations

impl<F: Field> EvaluationDomain<F>

pub fn from_points( finite_points: Vec<F>, with_infinity: bool, ) -> Result<Self, Error>

pub fn size(&self) -> usize

pub fn finite_points(&self) -> &[F]

pub const fn with_infinity(&self) -> bool

pub fn lagrange_evals<FE: ExtensionField<F>>(&self, x: FE) -> Vec<FE>

Compute a vector of Lagrange polynomial evaluations in $O(N)$ at a given point x.

For an evaluation domain consisting of points $\pi_i$ Lagrange polynomials $L_i(x)$ are defined by $$L_i(x) = \sum_{j \neq i}\frac{x - \pi_j}{\pi_i - \pi_j}$$

pub fn extrapolate<PE>(&self, values: &[PE], x: PE::Scalar) -> Result<PE, Error>

where PE: PackedField<Scalar: ExtensionField<F>>,

Evaluate the unique interpolated polynomial at any point, for a given set of values, in $O(N)$.

Trait Implementations

impl<F: Clone + Field> Clone for EvaluationDomain<F>

fn clone(&self) -> EvaluationDomain<F>

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<F: Debug + Field> Debug for EvaluationDomain<F>

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

Formats the value using the given formatter.

impl<F: Field> From<EvaluationDomain<F>> for InterpolationDomain<F>

fn from(evaluation_domain: EvaluationDomain<F>) -> Self

Converts to this type from the input type.