Struct snarkvm_algorithms::fft::domain::EvaluationDomain
source · [−]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,
}
Expand description
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
sourceimpl<F: FftField> EvaluationDomain<F>
impl<F: FftField> EvaluationDomain<F>
sourcepub fn sample_element_outside_domain<R: Rng>(&self, rng: &mut R) -> F
pub fn sample_element_outside_domain<R: Rng>(&self, rng: &mut R) -> F
Sample an element that is not in the domain.
sourcepub fn new(num_coeffs: usize) -> Option<Self>
pub fn new(num_coeffs: usize) -> Option<Self>
Construct a domain that is large enough for evaluations of a polynomial
having num_coeffs
coefficients.
sourcepub fn compute_size_of_domain(num_coeffs: usize) -> Option<usize>
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.
sourcepub fn fft<T: DomainCoeff<F>>(&self, coeffs: &[T]) -> Vec<T>
pub fn fft<T: DomainCoeff<F>>(&self, coeffs: &[T]) -> Vec<T>
Compute an FFT.
sourcepub fn fft_in_place<T: DomainCoeff<F>>(&self, coeffs: &mut Vec<T>)
pub fn fft_in_place<T: DomainCoeff<F>>(&self, coeffs: &mut Vec<T>)
Compute an FFT, modifying the vector in place.
sourcepub fn ifft<T: DomainCoeff<F>>(&self, evals: &[T]) -> Vec<T>
pub fn ifft<T: DomainCoeff<F>>(&self, evals: &[T]) -> Vec<T>
Compute an IFFT.
sourcepub fn ifft_in_place<T: DomainCoeff<F>>(&self, evals: &mut Vec<T>)
pub fn ifft_in_place<T: DomainCoeff<F>>(&self, evals: &mut Vec<T>)
Compute an IFFT, modifying the vector in place.
sourcepub fn coset_fft<T: DomainCoeff<F>>(&self, coeffs: &[T]) -> Vec<T>
pub fn coset_fft<T: DomainCoeff<F>>(&self, coeffs: &[T]) -> Vec<T>
Compute an FFT over a coset of the domain.
sourcepub fn coset_fft_in_place<T: DomainCoeff<F>>(&self, coeffs: &mut Vec<T>)
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.
sourcepub fn coset_ifft<T: DomainCoeff<F>>(&self, evals: &[T]) -> Vec<T>
pub fn coset_ifft<T: DomainCoeff<F>>(&self, evals: &[T]) -> Vec<T>
Compute an IFFT over a coset of the domain.
sourcepub fn coset_ifft_in_place<T: DomainCoeff<F>>(&self, evals: &mut Vec<T>)
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.
sourcepub fn evaluate_all_lagrange_coefficients(&self, tau: F) -> Vec<F>
pub fn evaluate_all_lagrange_coefficients(&self, tau: F) -> Vec<F>
Evaluate all the lagrange polynomials defined by this domain at the point
tau
.
sourcepub fn vanishing_polynomial(&self) -> SparsePolynomial<F>
pub fn vanishing_polynomial(&self) -> SparsePolynomial<F>
Return the sparse vanishing polynomial.
sourcepub fn evaluate_vanishing_polynomial(&self, tau: F) -> F
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
.
sourcepub fn elements(&self) -> Elements<F>ⓘNotable traits for Elements<F>impl<F: FftField> Iterator for Elements<F> type Item = F;
pub fn elements(&self) -> Elements<F>ⓘNotable traits for Elements<F>impl<F: FftField> Iterator for Elements<F> type Item = F;
Return an iterator over the elements of the domain.
sourcepub fn divide_by_vanishing_poly_on_coset_in_place(&self, evals: &mut [F])
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.
sourcepub fn reindex_by_subdomain(&self, other: Self, index: usize) -> usize
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.
sourcepub fn mul_polynomials_in_evaluation_domain(
&self,
self_evals: &[F],
other_evals: &[F]
) -> Vec<F>
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.
sourceimpl<F: FftField> EvaluationDomain<F>
impl<F: FftField> EvaluationDomain<F>
sourcepub fn roots_of_unity(&self, root: F) -> Vec<F>
pub fn roots_of_unity(&self, root: F) -> Vec<F>
Computes the first self.size / 2
roots of unity.
Trait Implementations
sourceimpl<F: FftField> CanonicalDeserialize for EvaluationDomain<F>
impl<F: FftField> CanonicalDeserialize for EvaluationDomain<F>
sourcefn deserialize<R: Read>(reader: &mut R) -> Result<Self, SerializationError>
fn deserialize<R: Read>(reader: &mut R) -> Result<Self, SerializationError>
Reads Self
from reader
.
sourcefn deserialize_uncompressed<R: Read>(
reader: &mut R
) -> Result<Self, SerializationError>
fn deserialize_uncompressed<R: Read>(
reader: &mut R
) -> Result<Self, SerializationError>
Reads Self
from reader
without compression.
sourceimpl<F: FftField> CanonicalSerialize for EvaluationDomain<F>
impl<F: FftField> CanonicalSerialize for EvaluationDomain<F>
sourcefn serialize<W: Write>(&self, writer: &mut W) -> Result<(), SerializationError>
fn serialize<W: Write>(&self, writer: &mut W) -> Result<(), SerializationError>
Serializes self
into writer
.
fn serialized_size(&self) -> usize
sourcefn serialize_uncompressed<W: Write>(
&self,
writer: &mut W
) -> Result<(), SerializationError>
fn serialize_uncompressed<W: Write>(
&self,
writer: &mut W
) -> Result<(), SerializationError>
Serializes self
into writer
without compression.
fn uncompressed_size(&self) -> usize
sourceimpl<F: Clone + FftField> Clone for EvaluationDomain<F>
impl<F: Clone + FftField> Clone for EvaluationDomain<F>
sourcefn clone(&self) -> EvaluationDomain<F>
fn clone(&self) -> EvaluationDomain<F>
Returns a copy of the value. Read more
1.0.0 · sourcefn clone_from(&mut self, source: &Self)
fn clone_from(&mut self, source: &Self)
Performs copy-assignment from source
. Read more
sourceimpl<F: FftField> Debug for EvaluationDomain<F>
impl<F: FftField> Debug for EvaluationDomain<F>
sourceimpl<F: Hash + FftField> Hash for EvaluationDomain<F>
impl<F: Hash + FftField> Hash for EvaluationDomain<F>
sourceimpl<F: PartialEq + FftField> PartialEq<EvaluationDomain<F>> for EvaluationDomain<F>
impl<F: PartialEq + FftField> PartialEq<EvaluationDomain<F>> for EvaluationDomain<F>
sourcefn eq(&self, other: &EvaluationDomain<F>) -> bool
fn eq(&self, other: &EvaluationDomain<F>) -> bool
This method tests for self
and other
values to be equal, and is used
by ==
. Read more
sourcefn ne(&self, other: &EvaluationDomain<F>) -> bool
fn ne(&self, other: &EvaluationDomain<F>) -> bool
This method tests for !=
.
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>
Auto Trait Implementations
impl<F> RefUnwindSafe for EvaluationDomain<F> where
F: RefUnwindSafe,
impl<F> Send for EvaluationDomain<F>
impl<F> Sync for EvaluationDomain<F>
impl<F> Unpin for EvaluationDomain<F> where
F: Unpin,
impl<F> UnwindSafe for EvaluationDomain<F> where
F: UnwindSafe,
Blanket Implementations
sourceimpl<T> BorrowMut<T> for T where
T: ?Sized,
impl<T> BorrowMut<T> for T where
T: ?Sized,
const: unstable · sourcepub fn borrow_mut(&mut self) -> &mut T
pub fn borrow_mut(&mut self) -> &mut T
Mutably borrows from an owned value. Read more
sourceimpl<Q, K> Equivalent<K> for Q where
Q: Eq + ?Sized,
K: Borrow<Q> + ?Sized,
impl<Q, K> Equivalent<K> for Q where
Q: Eq + ?Sized,
K: Borrow<Q> + ?Sized,
sourcepub fn equivalent(&self, key: &K) -> bool
pub fn equivalent(&self, key: &K) -> bool
Compare self to key
and return true
if they are equal.
impl<T> Pointable for T
impl<T> Pointable for T
sourceimpl<T> ToOwned for T where
T: Clone,
impl<T> ToOwned for T where
T: Clone,
type Owned = T
type Owned = T
The resulting type after obtaining ownership.
sourcepub fn to_owned(&self) -> T
pub fn to_owned(&self) -> T
Creates owned data from borrowed data, usually by cloning. Read more
sourcepub fn clone_into(&self, target: &mut T)
pub fn clone_into(&self, target: &mut T)
toowned_clone_into
)Uses borrowed data to replace owned data, usually by cloning. Read more