Function winter_math::fft::interpolate_poly_with_offset

pub fn interpolate_poly_with_offset<B, E>(
    evaluations: &mut [E], 
    inv_twiddles: &[B], 
    domain_offset: B
) where
    B: StarkField,
    E: FieldElement<BaseField = B>, 

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