[−][src]Module contest_algorithms::math::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() |