Struct halo2_proofs::poly::EvaluationDomain
source · pub struct EvaluationDomain<F>where
F: Field,{ /* private fields */ }
Expand description
This structure contains precomputed constants and other details needed for performing operations on an evaluation domain of size $2^k$ and an extended domain of size $2^{k} * j$ with $j \neq 0$.
Implementations§
source§impl<F> EvaluationDomain<F>where
F: WithSmallOrderMulGroup<3>,
impl<F> EvaluationDomain<F>where
F: WithSmallOrderMulGroup<3>,
sourcepub fn new(j: u32, k: u32) -> EvaluationDomain<F>
pub fn new(j: u32, k: u32) -> EvaluationDomain<F>
This constructs a new evaluation domain object based on the provided values $j, k$.
sourcepub fn lagrange_from_vec(&self, values: Vec<F>) -> Polynomial<F, LagrangeCoeff>
pub fn lagrange_from_vec(&self, values: Vec<F>) -> Polynomial<F, LagrangeCoeff>
Obtains a polynomial in Lagrange form when given a vector of Lagrange
coefficients of size n
; panics if the provided vector is the wrong
length.
sourcepub fn coeff_from_vec(&self, values: Vec<F>) -> Polynomial<F, Coeff>
pub fn coeff_from_vec(&self, values: Vec<F>) -> Polynomial<F, Coeff>
Obtains a polynomial in coefficient form when given a vector of
coefficients of size n
; panics if the provided vector is the wrong
length.
sourcepub fn empty_coeff(&self) -> Polynomial<F, Coeff>
pub fn empty_coeff(&self) -> Polynomial<F, Coeff>
Returns an empty (zero) polynomial in the coefficient basis
sourcepub fn empty_lagrange(&self) -> Polynomial<F, LagrangeCoeff>
pub fn empty_lagrange(&self) -> Polynomial<F, LagrangeCoeff>
Returns an empty (zero) polynomial in the Lagrange coefficient basis
sourcepub fn constant_lagrange(&self, scalar: F) -> Polynomial<F, LagrangeCoeff>
pub fn constant_lagrange(&self, scalar: F) -> Polynomial<F, LagrangeCoeff>
Returns a constant polynomial in the Lagrange coefficient basis
sourcepub fn empty_extended(&self) -> Polynomial<F, ExtendedLagrangeCoeff>
pub fn empty_extended(&self) -> Polynomial<F, ExtendedLagrangeCoeff>
Returns an empty (zero) polynomial in the extended Lagrange coefficient basis
sourcepub fn constant_extended(
&self,
scalar: F
) -> Polynomial<F, ExtendedLagrangeCoeff>
pub fn constant_extended( &self, scalar: F ) -> Polynomial<F, ExtendedLagrangeCoeff>
Returns a constant polynomial in the extended Lagrange coefficient basis
sourcepub fn lagrange_to_coeff(
&self,
a: Polynomial<F, LagrangeCoeff>
) -> Polynomial<F, Coeff>
pub fn lagrange_to_coeff( &self, a: Polynomial<F, LagrangeCoeff> ) -> Polynomial<F, Coeff>
This takes us from an n-length vector into the coefficient form.
This function will panic if the provided vector is not the correct length.
sourcepub fn coeff_to_extended(
&self,
a: Polynomial<F, Coeff>
) -> Polynomial<F, ExtendedLagrangeCoeff>
pub fn coeff_to_extended( &self, a: Polynomial<F, Coeff> ) -> Polynomial<F, ExtendedLagrangeCoeff>
This takes us from an n-length coefficient vector into a coset of the extended
evaluation domain, rotating by rotation
if desired.
pub fn lagrange_extended( &self, idx: usize ) -> Polynomial<F, ExtendedLagrangeCoeff>
sourcepub fn rotate_extended(
&self,
poly: &Polynomial<F, ExtendedLagrangeCoeff>,
rotation: Rotation
) -> Polynomial<F, ExtendedLagrangeCoeff>
pub fn rotate_extended( &self, poly: &Polynomial<F, ExtendedLagrangeCoeff>, rotation: Rotation ) -> Polynomial<F, ExtendedLagrangeCoeff>
Rotate the extended domain polynomial over the original domain.
sourcepub fn extended_to_coeff(
&self,
a: Polynomial<F, ExtendedLagrangeCoeff>
) -> Vec<F>
pub fn extended_to_coeff( &self, a: Polynomial<F, ExtendedLagrangeCoeff> ) -> Vec<F>
This takes us from the extended evaluation domain and gets us the quotient polynomial coefficients.
This function will panic if the provided vector is not the correct length.
sourcepub fn divide_by_vanishing_poly(
&self,
a: Polynomial<F, ExtendedLagrangeCoeff>
) -> Polynomial<F, ExtendedLagrangeCoeff>
pub fn divide_by_vanishing_poly( &self, a: Polynomial<F, ExtendedLagrangeCoeff> ) -> Polynomial<F, ExtendedLagrangeCoeff>
This divides the polynomial (in the extended domain) by the vanishing polynomial of the $2^k$ size domain.
sourcepub fn extended_k(&self) -> u32
pub fn extended_k(&self) -> u32
Get the size of the extended domain
sourcepub fn extended_len(&self) -> usize
pub fn extended_len(&self) -> usize
Get the size of the extended domain
sourcepub fn get_omega(&self) -> F
pub fn get_omega(&self) -> F
Get $\omega$, the generator of the $2^k$ order multiplicative subgroup.
sourcepub fn get_omega_inv(&self) -> F
pub fn get_omega_inv(&self) -> F
Get $\omega^{-1}$, the inverse of the generator of the $2^k$ order multiplicative subgroup.
sourcepub fn get_extended_omega(&self) -> F
pub fn get_extended_omega(&self) -> F
Get the generator of the extended domain’s multiplicative subgroup.
sourcepub fn rotate_omega(&self, value: F, rotation: Rotation) -> F
pub fn rotate_omega(&self, value: F, rotation: Rotation) -> F
Multiplies a value by some power of $\omega$, essentially rotating over the domain.
sourcepub fn l_i_range<I>(&self, x: F, xn: F, rotations: I) -> Vec<F>
pub fn l_i_range<I>(&self, x: F, xn: F, rotations: I) -> Vec<F>
Computes evaluations (at the point x
, where xn = x^n
) of Lagrange
basis polynomials l_i(X)
defined such that l_i(omega^i) = 1
and
l_i(omega^j) = 0
for all j != i
at each provided rotation i
.
§Implementation
The polynomial $$\prod_{j=0,j \neq i}^{n - 1} (X - \omega^j)$$ has a root at all points in the domain except $\omega^i$, where it evaluates to $$\prod_{j=0,j \neq i}^{n - 1} (\omega^i - \omega^j)$$ and so we divide that polynomial by this value to obtain $l_i(X)$. Since $$\prod_{j=0,j \neq i}^{n - 1} (X - \omega^j) = \frac{X^n - 1}{X - \omega^i}$$ then $l_i(x)$ for some $x$ is evaluated as $$\left(\frac{x^n - 1}{x - \omega^i}\right) \cdot \left(\frac{1}{\prod_{j=0,j \neq i}^{n - 1} (\omega^i - \omega^j)}\right).$$ We refer to $$1 \over \prod_{j=0,j \neq i}^{n - 1} (\omega^i - \omega^j)$$ as the barycentric weight of $\omega^i$.
We know that for $i = 0$ $$\frac{1}{\prod_{j=0,j \neq i}^{n - 1} (\omega^i - \omega^j)} = \frac{1}{n}.$$
If we multiply $(1 / n)$ by $\omega^i$ then we obtain $$\frac{1}{\prod_{j=0,j \neq 0}^{n - 1} (\omega^i - \omega^j)} = \frac{1}{\prod_{j=0,j \neq i}^{n - 1} (\omega^i - \omega^j)}$$ which is the barycentric weight of $\omega^i$.
sourcepub fn get_quotient_poly_degree(&self) -> usize
pub fn get_quotient_poly_degree(&self) -> usize
Gets the quotient polynomial’s degree (as a multiple of n)
sourcepub fn pinned(&self) -> PinnedEvaluationDomain<'_, F>
pub fn pinned(&self) -> PinnedEvaluationDomain<'_, F>
Obtain a pinned version of this evaluation domain; a structure with the minimal parameters needed to determine the rest of the evaluation domain.
Trait Implementations§
source§impl<F> Clone for EvaluationDomain<F>
impl<F> Clone for EvaluationDomain<F>
source§fn clone(&self) -> EvaluationDomain<F>
fn clone(&self) -> EvaluationDomain<F>
1.0.0 · source§fn clone_from(&mut self, source: &Self)
fn clone_from(&mut self, source: &Self)
source
. Read moreAuto Trait Implementations§
impl<F> Freeze for EvaluationDomain<F>where
F: Freeze,
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§
source§impl<T> BorrowMut<T> for Twhere
T: ?Sized,
impl<T> BorrowMut<T> for Twhere
T: ?Sized,
source§fn borrow_mut(&mut self) -> &mut T
fn borrow_mut(&mut self) -> &mut T
§impl<T> Conv for T
impl<T> Conv for T
§impl<T> FmtForward for T
impl<T> FmtForward for T
§fn fmt_binary(self) -> FmtBinary<Self>where
Self: Binary,
fn fmt_binary(self) -> FmtBinary<Self>where
Self: Binary,
self
to use its Binary
implementation when Debug
-formatted.§fn fmt_display(self) -> FmtDisplay<Self>where
Self: Display,
fn fmt_display(self) -> FmtDisplay<Self>where
Self: Display,
self
to use its Display
implementation when
Debug
-formatted.§fn fmt_lower_exp(self) -> FmtLowerExp<Self>where
Self: LowerExp,
fn fmt_lower_exp(self) -> FmtLowerExp<Self>where
Self: LowerExp,
self
to use its LowerExp
implementation when
Debug
-formatted.§fn fmt_lower_hex(self) -> FmtLowerHex<Self>where
Self: LowerHex,
fn fmt_lower_hex(self) -> FmtLowerHex<Self>where
Self: LowerHex,
self
to use its LowerHex
implementation when
Debug
-formatted.§fn fmt_octal(self) -> FmtOctal<Self>where
Self: Octal,
fn fmt_octal(self) -> FmtOctal<Self>where
Self: Octal,
self
to use its Octal
implementation when Debug
-formatted.§fn fmt_pointer(self) -> FmtPointer<Self>where
Self: Pointer,
fn fmt_pointer(self) -> FmtPointer<Self>where
Self: Pointer,
self
to use its Pointer
implementation when
Debug
-formatted.§fn fmt_upper_exp(self) -> FmtUpperExp<Self>where
Self: UpperExp,
fn fmt_upper_exp(self) -> FmtUpperExp<Self>where
Self: UpperExp,
self
to use its UpperExp
implementation when
Debug
-formatted.§fn fmt_upper_hex(self) -> FmtUpperHex<Self>where
Self: UpperHex,
fn fmt_upper_hex(self) -> FmtUpperHex<Self>where
Self: UpperHex,
self
to use its UpperHex
implementation when
Debug
-formatted.§fn fmt_list(self) -> FmtList<Self>where
&'a Self: for<'a> IntoIterator,
fn fmt_list(self) -> FmtList<Self>where
&'a Self: for<'a> IntoIterator,
§impl<T> Instrument for T
impl<T> Instrument for T
§fn instrument(self, span: Span) -> Instrumented<Self>
fn instrument(self, span: Span) -> Instrumented<Self>
§fn in_current_span(self) -> Instrumented<Self>
fn in_current_span(self) -> Instrumented<Self>
source§impl<T> IntoEither for T
impl<T> IntoEither for T
source§fn into_either(self, into_left: bool) -> Either<Self, Self>
fn into_either(self, into_left: bool) -> Either<Self, Self>
self
into a Left
variant of Either<Self, Self>
if into_left
is true
.
Converts self
into a Right
variant of Either<Self, Self>
otherwise. Read moresource§fn into_either_with<F>(self, into_left: F) -> Either<Self, Self>
fn into_either_with<F>(self, into_left: F) -> Either<Self, Self>
self
into a Left
variant of Either<Self, Self>
if into_left(&self)
returns true
.
Converts self
into a Right
variant of Either<Self, Self>
otherwise. Read more§impl<T> Pipe for Twhere
T: ?Sized,
impl<T> Pipe for Twhere
T: ?Sized,
§fn pipe<R>(self, func: impl FnOnce(Self) -> R) -> Rwhere
Self: Sized,
fn pipe<R>(self, func: impl FnOnce(Self) -> R) -> Rwhere
Self: Sized,
§fn pipe_ref<'a, R>(&'a self, func: impl FnOnce(&'a Self) -> R) -> Rwhere
R: 'a,
fn pipe_ref<'a, R>(&'a self, func: impl FnOnce(&'a Self) -> R) -> Rwhere
R: 'a,
self
and passes that borrow into the pipe function. Read more§fn pipe_ref_mut<'a, R>(&'a mut self, func: impl FnOnce(&'a mut Self) -> R) -> Rwhere
R: 'a,
fn pipe_ref_mut<'a, R>(&'a mut self, func: impl FnOnce(&'a mut Self) -> R) -> Rwhere
R: 'a,
self
and passes that borrow into the pipe function. Read more§fn pipe_borrow<'a, B, R>(&'a self, func: impl FnOnce(&'a B) -> R) -> R
fn pipe_borrow<'a, B, R>(&'a self, func: impl FnOnce(&'a B) -> R) -> R
§fn pipe_borrow_mut<'a, B, R>(
&'a mut self,
func: impl FnOnce(&'a mut B) -> R
) -> R
fn pipe_borrow_mut<'a, B, R>( &'a mut self, func: impl FnOnce(&'a mut B) -> R ) -> R
§fn pipe_as_ref<'a, U, R>(&'a self, func: impl FnOnce(&'a U) -> R) -> R
fn pipe_as_ref<'a, U, R>(&'a self, func: impl FnOnce(&'a U) -> R) -> R
self
, then passes self.as_ref()
into the pipe function.§fn pipe_as_mut<'a, U, R>(&'a mut self, func: impl FnOnce(&'a mut U) -> R) -> R
fn pipe_as_mut<'a, U, R>(&'a mut self, func: impl FnOnce(&'a mut U) -> R) -> R
self
, then passes self.as_mut()
into the pipe
function.§fn pipe_deref<'a, T, R>(&'a self, func: impl FnOnce(&'a T) -> R) -> R
fn pipe_deref<'a, T, R>(&'a self, func: impl FnOnce(&'a T) -> R) -> R
self
, then passes self.deref()
into the pipe function.§impl<T> Pointable for T
impl<T> Pointable for T
§impl<T> Tap for T
impl<T> Tap for T
§fn tap_borrow<B>(self, func: impl FnOnce(&B)) -> Self
fn tap_borrow<B>(self, func: impl FnOnce(&B)) -> Self
Borrow<B>
of a value. Read more§fn tap_borrow_mut<B>(self, func: impl FnOnce(&mut B)) -> Self
fn tap_borrow_mut<B>(self, func: impl FnOnce(&mut B)) -> Self
BorrowMut<B>
of a value. Read more§fn tap_ref<R>(self, func: impl FnOnce(&R)) -> Self
fn tap_ref<R>(self, func: impl FnOnce(&R)) -> Self
AsRef<R>
view of a value. Read more§fn tap_ref_mut<R>(self, func: impl FnOnce(&mut R)) -> Self
fn tap_ref_mut<R>(self, func: impl FnOnce(&mut R)) -> Self
AsMut<R>
view of a value. Read more§fn tap_deref<T>(self, func: impl FnOnce(&T)) -> Self
fn tap_deref<T>(self, func: impl FnOnce(&T)) -> Self
Deref::Target
of a value. Read more§fn tap_deref_mut<T>(self, func: impl FnOnce(&mut T)) -> Self
fn tap_deref_mut<T>(self, func: impl FnOnce(&mut T)) -> Self
Deref::Target
of a value. Read more§fn tap_dbg(self, func: impl FnOnce(&Self)) -> Self
fn tap_dbg(self, func: impl FnOnce(&Self)) -> Self
.tap()
only in debug builds, and is erased in release builds.§fn tap_mut_dbg(self, func: impl FnOnce(&mut Self)) -> Self
fn tap_mut_dbg(self, func: impl FnOnce(&mut Self)) -> Self
.tap_mut()
only in debug builds, and is erased in release
builds.§fn tap_borrow_dbg<B>(self, func: impl FnOnce(&B)) -> Self
fn tap_borrow_dbg<B>(self, func: impl FnOnce(&B)) -> Self
.tap_borrow()
only in debug builds, and is erased in release
builds.§fn tap_borrow_mut_dbg<B>(self, func: impl FnOnce(&mut B)) -> Self
fn tap_borrow_mut_dbg<B>(self, func: impl FnOnce(&mut B)) -> Self
.tap_borrow_mut()
only in debug builds, and is erased in release
builds.§fn tap_ref_dbg<R>(self, func: impl FnOnce(&R)) -> Self
fn tap_ref_dbg<R>(self, func: impl FnOnce(&R)) -> Self
.tap_ref()
only in debug builds, and is erased in release
builds.§fn tap_ref_mut_dbg<R>(self, func: impl FnOnce(&mut R)) -> Self
fn tap_ref_mut_dbg<R>(self, func: impl FnOnce(&mut R)) -> Self
.tap_ref_mut()
only in debug builds, and is erased in release
builds.§fn tap_deref_dbg<T>(self, func: impl FnOnce(&T)) -> Self
fn tap_deref_dbg<T>(self, func: impl FnOnce(&T)) -> Self
.tap_deref()
only in debug builds, and is erased in release
builds.