Struct snarkvm_algorithms::fft::domain::EvaluationDomain

pub struct EvaluationDomain<F: FftField> {
    pub size: u64,
    pub log_size_of_group: u32,
    pub size_as_field_element: F,
    pub size_inv: F,
    pub group_gen: F,
    pub group_gen_inv: F,
    pub generator_inv: F,
}

Defines a domain over which finite field (I)FFTs can be performed. Works only for fields that have a large multiplicative subgroup of size that is a power-of-2.

Fields

size: u64

The size of the domain.

log_size_of_group: u32

log_2(self.size).

size_as_field_element: F

Size of the domain as a field element.

size_inv: F

Inverse of the size in the field.

group_gen: F

A generator of the subgroup.

group_gen_inv: F

Inverse of the generator of the subgroup.

generator_inv: F

Multiplicative generator of the finite field.

Implementations

impl<F: FftField> EvaluationDomain<F>

pub fn sample_element_outside_domain<R: Rng>(&self, rng: &mut R) -> F

Sample an element that is not in the domain.

pub fn new(num_coeffs: usize) -> Option<Self>

Construct a domain that is large enough for evaluations of a polynomial having num_coeffs coefficients.

pub fn compute_size_of_domain(num_coeffs: usize) -> Option<usize>

Return the size of a domain that is large enough for evaluations of a polynomial having num_coeffs coefficients.

pub fn size(&self) -> usize

Return the size of self.

pub fn fft<T: DomainCoeff<F>>(&self, coeffs: &[T]) -> Vec<T>

Compute an FFT.

pub fn fft_in_place<T: DomainCoeff<F>>(&self, coeffs: &mut Vec<T>)

Compute an FFT, modifying the vector in place.

pub fn ifft<T: DomainCoeff<F>>(&self, evals: &[T]) -> Vec<T>

Compute an IFFT.

pub fn ifft_in_place<T: DomainCoeff<F>>(&self, evals: &mut Vec<T>)

Compute an IFFT, modifying the vector in place.

pub fn coset_fft<T: DomainCoeff<F>>(&self, coeffs: &[T]) -> Vec<T>

Compute an FFT over a coset of the domain.

pub fn coset_fft_in_place<T: DomainCoeff<F>>(&self, coeffs: &mut Vec<T>)

Compute an FFT over a coset of the domain, modifying the input vector in place.

pub fn coset_ifft<T: DomainCoeff<F>>(&self, evals: &[T]) -> Vec<T>

Compute an IFFT over a coset of the domain.

pub fn coset_ifft_in_place<T: DomainCoeff<F>>(&self, evals: &mut Vec<T>)

Compute an IFFT over a coset of the domain, modifying the input vector in place.

pub fn evaluate_all_lagrange_coefficients(&self, tau: F) -> Vec<F>

Evaluate all the lagrange polynomials defined by this domain at the point tau.

pub fn vanishing_polynomial(&self) -> SparsePolynomial<F>

Return the sparse vanishing polynomial.

pub fn evaluate_vanishing_polynomial(&self, tau: F) -> F

This evaluates the vanishing polynomial for this domain at tau. For multiplicative subgroups, this polynomial is z(X) = X^self.size - 1.

pub fn elements(&self) -> Elements<F>

Return an iterator over the elements of the domain.

pub fn divide_by_vanishing_poly_on_coset_in_place(&self, evals: &mut [F])

The target polynomial is the zero polynomial in our evaluation domain, so we must perform division over a coset.

pub fn reindex_by_subdomain(&self, other: &Self, index: usize) -> usize

Given an index which assumes the first elements of this domain are the elements of another (sub)domain with size size_s, this returns the actual index into this domain.

pub fn mul_polynomials_in_evaluation_domain(
    &self,
    self_evals: &[F],
    other_evals: &[F]
) -> Vec<F>

Perform O(n) multiplication of two polynomials that are presented by their evaluations in the domain. Returns the evaluations of the product over the domain.

impl<F: FftField> EvaluationDomain<F>

pub fn precompute_fft(&self) -> FFTPrecomputation<F>

pub fn precompute_ifft(&self) -> IFFTPrecomputation<F>

pub fn in_order_fft_with_pc<T: DomainCoeff<F>>(
    &self,
    x_s: &[T],
    pc: &FFTPrecomputation<F>
) -> Vec<T>

pub fn roots_of_unity(&self, root: F) -> Vec<F>

Computes the first self.size / 2 roots of unity.

Trait Implementations

impl<F: FftField> CanonicalDeserialize for EvaluationDomain<F>

fn deserialize_with_mode<R: Read>(
    reader: R,
    compress: Compress,
    validate: Validate
) -> Result<Self, SerializationError>

fn deserialize_compressed<R>(reader: R) -> Result<Self, SerializationError>where
    R: Read,

fn deserialize_compressed_unchecked<R>(
    reader: R
) -> Result<Self, SerializationError>where
    R: Read,

fn deserialize_uncompressed<R>(reader: R) -> Result<Self, SerializationError>where
    R: Read,

fn deserialize_uncompressed_unchecked<R>(
    reader: R
) -> Result<Self, SerializationError>where
    R: Read,

impl<F: FftField> CanonicalSerialize for EvaluationDomain<F>

fn serialize_with_mode<W: Write>(
    &self,
    writer: W,
    compress: Compress
) -> Result<(), SerializationError>

fn serialized_size(&self, compress: Compress) -> usize

fn serialize_compressed<W>(&self, writer: W) -> Result<(), SerializationError>where
    W: Write,

fn compressed_size(&self) -> usize

fn serialize_uncompressed<W>(&self, writer: W) -> Result<(), SerializationError>where
    W: Write,

fn uncompressed_size(&self) -> usize

impl<F: Clone + FftField> 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: FftField> Debug for EvaluationDomain<F>

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

Formats the value using the given formatter.

impl<F: Hash + FftField> Hash for EvaluationDomain<F>

fn hash<__H: Hasher>(&self, state: &mut __H)

Feeds this value into the given Hasher.

fn hash_slice<H>(data: &[Self], state: &mut H)where
    H: Hasher,
    Self: Sized,

Feeds a slice of this type into the given Hasher.

impl<F: PartialEq + FftField> PartialEq<EvaluationDomain<F>> for EvaluationDomain<F>

fn eq(&self, other: &EvaluationDomain<F>) -> bool

This method tests for self and other values to be equal, and is used by ==.

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

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

impl<F: PrimeField> SelectorPolynomial<F> for EvaluationDomain<F>

fn evaluate_selector_polynomial(&self, other: EvaluationDomain<F>, point: F) -> F

impl<F: PrimeField> UnnormalizedBivariateLagrangePoly<F> for EvaluationDomain<F>

fn eval_unnormalized_bivariate_lagrange_poly(&self, x: F, y: F) -> F

Evaluate the polynomial

fn batch_eval_unnormalized_bivariate_lagrange_poly_with_diff_inputs_over_domain(
    &self,
    x: F,
    domain: &EvaluationDomain<F>
) -> Vec<F>

fn batch_eval_unnormalized_bivariate_lagrange_poly_with_diff_inputs(
    &self,
    x: F
) -> Vec<F>

Evaluate over a batch of inputs

fn batch_eval_unnormalized_bivariate_lagrange_poly_with_same_inputs(
    &self
) -> Vec<F>

Evaluate the magic polynomial over self

impl<F: FftField> Valid for EvaluationDomain<F>

fn check(&self) -> Result<(), SerializationError>

fn batch_check<'a>(
    batch: impl Iterator<Item = &'a Self> + Send
) -> Result<(), SerializationError>where
    Self: 'a,

impl<F: Copy + FftField> Copy for EvaluationDomain<F>

impl<F: Eq + FftField> Eq for EvaluationDomain<F>

impl<F: FftField> StructuralEq for EvaluationDomain<F>

impl<F: FftField> StructuralPartialEq for EvaluationDomain<F>