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