Fast Fourier Transform, Algorithms, Pattern Matching, Convolution, Combination Sum.
values r(w^j). Here is the algorithm: Here is the updated FFT code from the previous post. def fft(poly, omega): n = len(poly) if n == 1: return [poly[0], poly[0]] even_fft = fft(poly[::2], omega*omega) odd_fft = fft(poly[1::2], omega*omega) m = int(n/2) result = [0]*2*m h = 1 for i in range(m):