Module winter_math::fft

FFT-based polynomial evaluation and interpolation.

Functions in this module can be used to evaluate and interpolate polynomials over domains which are multiplicative subgroups of finite fields and have lengths equal to powers of two. As compared to evaluation and interpolation functions available in the polynom module, these functions are much more efficient: their runtime complexity is O(n log n), where n is the domain size.

Functions

evaluate_poly

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

evaluate_poly_with_offset

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

get_inv_twiddles

Returns a set of inverse twiddles for the specified domain size.

get_twiddles

Returns a set of twiddles for the specified domain size.

infer_degree

Returns the degree of a polynomial implied by the provided evaluations.

interpolate_poly

Interpolates evaluations of a polynomial over the specified domain into a polynomial in coefficient from using the FFT algorithm.

interpolate_poly_with_offset

Interpolates evaluations of a polynomial over the specified (shifted) domain into a polynomial in coefficient from using the FFT algorithm.

serial_fft

Executes a single-threaded version of the FFT algorithm on the provided values.