Universal fast Fourier transform algorithm for prime data vector sizes
Ryszard Stasiński · 2004
In the paper it is shown that discrete Fourier transform can be computed using only 0(NlogN) operations even if N is prime, N is the transform size. A fast algorithm working for any prime N is presented, which worst case computational complexity is below 32N log/sub 2/(N) arithmetical operations, which can be compared to less than 4Nlog/sub 2/(N) operations for the best existing FFT for N being power of number 2. It is shown, however that by introducing few modifications the worst case computational complexity of the algorithm can be reduced to circa 16Nlog/sub 2/(N) arithmetical operations. In this way an interesting theoretical result is obtained that computational complexities of the DFT for 'most' and 'least' convenient N values do not differ by more than factor 4.