pub fn evaluate_poly_with_offset<B, E>(
p: &[E],
twiddles: &[B],
domain_offset: B,
blowup_factor: usize,
) -> Vec<E>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 notp.len()
/ 2. - Field specified by
B
does not contain a multiplicative subgroup of sizep.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);