Function winter_math::fft::interpolate_poly_with_offset
source · pub fn interpolate_poly_with_offset<B, E>(
evaluations: &mut [E],
inv_twiddles: &[B],
domain_offset: B
)where
B: StarkField,
E: FieldElement<BaseField = B>,
Expand description
Interpolates evaluations of a polynomial over the specified (shifted) domain into a polynomial in coefficient from using the FFT algorithm.
Uses the inverse FFT
algorithm to interpolate a polynomial from its evaluations over a domain defined by the
length of evaluations
and shifted by the domain_offset
in the field specified by the B
type parameter. The interpolation is done in-place, meaning no additional memory is allocated
and the evaluations contained in evaluations
are replaced with polynomial coefficients.
The complexity of interpolation is O(n
log(n
)), where n
is the size of the domain.
The size of the domain is assumed to be equal to evaluations.len()
which must be a power
of two. The base field specified by B
must have a multiplicative subgroup of size equal
to evaluations.len()
.
The shifted domain is defined as the original domain with every element multiplied by the
domain_offset
.
The inv_twiddles
needed for interpolation can be obtained via fft::get_inv_twiddles()
function using evaluations.len()
as the domain size parameter. This implies that
twiddles.len()
must be equal to evaluations.len()
/ 2.
When concurrent
feature is enabled, the interpolation is done in multiple threads.
Panics
Panics if:
- Length of
evaluations
is not a power of two. - Length of
inv_twiddles
is notevaluations.len()
/ 2. - Field specified by
B
does not contain a multiplicative subgroup of sizeevaluations.len()
. domain_offset
is ZERO.
Examples
let n = 2048;
let offset = BaseElement::GENERATOR;
// build a random polynomial
let p: Vec<BaseElement> = rand_vector(n);
// evaluate the polynomial over the domain using regular polynomial evaluation
let g = BaseElement::get_root_of_unity(n.ilog2());
let domain = get_power_series(g, n);
let shifted_domain = domain.iter().map(|&x| x * offset).collect::<Vec<_>>();
let mut ys = polynom::eval_many(&p, &shifted_domain);
// interpolate the evaluations into a polynomial
let inv_twiddles = get_inv_twiddles::<BaseElement>(ys.len());
interpolate_poly_with_offset(&mut ys, &inv_twiddles, offset);
assert_eq!(p, ys);