Function miden_processor::math::fft::interpolate_poly

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 not evaluations.len() / 2.
  • Field specified by B does not contain a multiplicative subgroup of size evaluations.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);