Function miden_processor::math::fft::evaluate_poly_with_offset

pub fn evaluate_poly_with_offset<B, E>(
    p: &[E],
    twiddles: &[B],
    domain_offset: B,
    blowup_factor: usize
) -> Vec<E, Global>where
    B: StarkField,
    E: FieldElement<BaseField = B>,
Expand description

Evaluates a polynomial on all points of the specified (shifted) 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, expanded by the blowup_factor, and shifted by the domain_offset in the field specified by the B type parameter. 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() * blowup_factor both of which must be powers of two. The base field specified by B must have a multiplicative subgroup of size equal to p.len() * blowup_factor.

The shifted domain is defined as the original domain with every element multiplied by the domain_offset.

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.
  • blowup_factor 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().
  • domain_offset is ZERO.

Examples

let n = 2048;
let offset = BaseElement::GENERATOR;
let blowup_factor = 2;

// build a random polynomial
let mut p: Vec<BaseElement> = rand_vector(n / blowup_factor);

// 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 expected = polynom::eval_many(&p, &shifted_domain);

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

assert_eq!(expected, actual);