算法造就的,2的幂次方采样点数和非2幂次方采样点数算法不同
你可以看看帮助文件中关于算法的这一段内容
Algorithm
The FFT functions (fft, fft2, fftn, ifft, ifft2, ifftn) are based on a library called FFTW [3],[4]. To compute an N-point DFT when N is composite (that is, when N = N1N2), the FFTW library decomposes the problem using the Cooley-Tukey algorithm [1], which first computes N1 transforms of size N2, and then computes N2 transforms of size N1. The decomposition is applied recursively to both the N1- and N2-point DFTs until the problem can be solved using one of several machine-generated fixed-size "codelets." The codelets in turn use several algorithms in combination, including a variation of Cooley-Tukey [5], a prime factor algorithm [6], and a split-radix algorithm [2]. The particular factorization of N is chosen heuristically.
When N is a prime number, the FFTW library first decomposes an N-point problem into three (N-1)-point problems using Rader's algorithm [7]. It then uses the Cooley-Tukey decomposition described above to compute the (N-1)-point DFTs.
For most N, real-input DFTs require roughly half the computation time of complex-input DFTs. However, when N has large prime factors, there is little or no speed difference.
The execution time for fft depends on the length of the transform. It is fastest for powers of two. It is almost as fast for lengths that have only small prime factors. It is typically several times slower for lengths that are prime or which have large prime factors. |