Fast Fourier Transform

fft.fft.fft(polynomial: fft.polynomial.Polynomial, roots_of_unity: Optional[fft.roots_of_unity.NthRootsOfUnity] = None) → list

This is a simple implementation of the Fast Fourier Transform (FFT).

The FFT is an efficient algorithm for the Discrete Fourier Transform. This implementation converts polynomials from a coefficient representation to a sample representation.

What makes the FFT ‘fast’ is the clever choice of inputs used to evaluate the polynomial, at two points, almost simultaneously. This combined with the fact that polynomials can be split into even and odd pairs in the following way:

f(x) = e(x^2) + x*o(x^2)

allows to create a divide and conquer algorithm that can evaluate a degree n polynomial at, at least, n points in O(n*log(n)).

fft.fft.smallest_power_of_two_not_less_than(n: int)

Does what it says on the tin.