Module fft

The Fast Fourier Transform (FFT) and Number Theoretic Transform (NTT)

Traits

FFT

Functions

convolution

Given two polynomials (vectors) sum_i a[i] x^i and sum_i b[i] x^i, computes their product (convolution) c[k] = sum_(i+j=k) a[i]*b[j]. Uses complex FFT if inputs are f64, or modular NTT if inputs are i64.

dft_from_reals

From a slice of reals (f64 or i64), computes DFT of size at least desired_len

fft

Computes the discrete fourier transform of v, whose length is a power of 2. Forward transform: polynomial coefficients -> evaluate at roots of unity Inverse transform: values at roots of unity -> interpolated coefficients

idft_to_reals

The inverse of dft_from_reals()