Fast Fourier Transform, Algorithms, Pattern Matching, Convolution, Combination Sum.
result[i] = (even_fft[i] + h*odd_fft[i]) result[i+m] = (even_fft[i] - h*odd_fft[i]) h *= omega return result Note that, in this implementation we are passing w as a paratemeter to the recursion because each sub-recursion uses w². Python implementation for multiplying 2 integers using the FFT