Function winter_math::fft::interpolate_poly
source · pub fn interpolate_poly<B, E>(evaluations: &mut [E], inv_twiddles: &[B])where
B: StarkField,
E: FieldElement<BaseField = B>,
Expand description
Interpolates evaluations of a polynomial over the specified 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
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 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()
.
Examples
let n = 2048;
// 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 mut ys = polynom::eval_many(&p, &domain);
// interpolate the evaluations into a polynomial
let inv_twiddles = get_inv_twiddles::<BaseElement>(ys.len());
interpolate_poly(&mut ys, &inv_twiddles);
assert_eq!(p, ys);