Need help for optimizing FFT runtime

Правка en1, от haleyk100198, 2017-01-09 08:31:48

I was practising FFT with some problems, but I found out that my implementation of FFT seems to take longer than what it takes to fit into the TL.

For the problem 528D. Fuzzy Search (I understand that the problem also has a bitmask solution, but I'd like to practise FFT), I implemented the FFT algorithm (code here) for the string comparison, yet it takes more than 3 seconds to compute 12 FFT(and inverse) of a vector with a size of (2^18).

I wonder how I can improve my implementation's runtime?

Теги fft, 528d

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский haleyk100198 2017-01-09 08:31:48 619 Initial revision (published)