Function miden_processor::math::fft::evaluate_poly

pub fn evaluate_poly<B, E>(p: &mut [E], twiddles: &[B])where
    B: StarkField,
    E: FieldElement<BaseField = B>,
Expand description

Evaluates a polynomial on all points of the specified domain using the FFT algorithm.

Uses the FFT algorithm to evaluate polynomial p on all points of a domain defined by the length of p in the field specified by the B type parameter. The evaluation is done in-place, meaning no additional memory is allocated and p is updated with results of the evaluation. The polynomial p is expected to be in coefficient form.

The complexity of evaluation is O(n log(n)), where n is the size of the domain.

The size of the domain is assumed to be equal to p.len() which must be a power of two. The base field specified by B must have a multiplicative subgroup of size equal to p.len().

The twiddles needed for evaluation can be obtained via fft::get_twiddles() function using p.len() as the domain size parameter. This implies that twiddles.len() must be equal to p.len() / 2.

When concurrent feature is enabled, the evaluation is done in multiple threads.

Panics

Panics if:

  • Length of p is not a power of two.
  • Length of twiddles is not p.len() / 2.
  • Field specified by B does not contain a multiplicative subgroup of size p.len().

Examples

let n = 2048;

// build a random polynomial
let mut 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 expected = polynom::eval_many(&p, &domain);

// evaluate the polynomial over the domain using FFT-based evaluation
let twiddles = get_twiddles::<BaseElement>(p.len());
evaluate_poly(&mut p, &twiddles);

assert_eq!(expected, p);