CFT의 fftw가 2의 제곱에 비해 느려 집니까?

Question

저는 C++에서 fftw 라이브러리로 작업하고 있습니다. 나는 fft의 계산이 2의 거듭 제곱에 대해 가장 효율적이라는 것을 알고 있지만, 2 차원 fft의 최소 예를 만들었고 나는 다른 결과를 얻었습니다. 2의 힘이없는 2 차원 fft는 다른 것보다 훨씬 빠르게 계산됩니다. 신호 A (비 전력의-2)의 경우 : 나는 N 및 M. 내 용 프로그램의 반환에 대한 소수를 choosed 할

int N = 2083; 
int M = 2087; 
int Npow2 = pow(2, ceil(log2(N))); 
int Mpow2 = pow(2, ceil(log2(M))); 

fftw_complex * signala = (fftw_complex *)fftw_malloc(sizeof(fftw_complex)* N * M); 

for (int i = 0; i < N; i++) 
{ 
    for (int j = 0; j < M; j++) 
    { 
     signala[i*M + j][0] = rand(); 
     signala[i*M + j][0] = 0; 
    } 
} 

fftw_complex * signala_ext = (fftw_complex *)fftw_malloc(sizeof(fftw_complex)* Npow2 * Mpow2); 

fftw_complex * outa = (fftw_complex *)fftw_malloc(sizeof(fftw_complex)* N * M); 
fftw_complex * outaext = (fftw_complex *)fftw_malloc(sizeof(fftw_complex)* Npow2 * Mpow2); 

//Create Plans 
fftw_plan pa = fftw_plan_dft_2d(N, M, signala, outa, FFTW_FORWARD, FFTW_ESTIMATE); 
fftw_plan paext = fftw_plan_dft_2d(Npow2, Mpow2, signala_ext, outaext, FFTW_FORWARD, FFTW_ESTIMATE); 

//zeropadding 
memset(signala_ext, 0, sizeof(fftw_complex)* Npow2 * Mpow2); //Null setzen 
for (int i = 0; i < N; i++) 
{ 
    for (int j = 0; j < M; j++) 
    { 
     signala_ext[i*Mpow2 + j][0] = signala[i*M + j][0]; 
     signala_ext[i*Mpow2 + j][1] = signala[i*M + j][1]; 
    } 
} 

//Execute FFT 
double tstart1 = clock(); 

fftw_execute(pa); 

double time1 = (clock() - tstart1)/CLOCKS_PER_SEC; 
printf("Time: %f sec\n", time1); 
double tstart2 = clock(); 

fftw_execute(paext); 

double time2 = (clock() - tstart2)/CLOCKS_PER_SEC; 
printf("Time: %f sec\n", time2); 

: 여기 내 코드입니다 signala_ext를 들어 2.95 초 (전원의-2) : 5.232 초

2의 거듭 제곱을 가진 fft가 왜 그렇게 느린가요? 나는 무엇을 잘못 했는가?

도움에 감사드립니다.

Answer 1

FFTW는 작은 소수의 거듭 제곱의 곱인 차원을 좋아합니다. 이 기준을 만족하는 2083 또는 2087보다 가까운 가장 가까운 값은 2100 (2100 = 2 * 3 * 5 * 7)이므로 2100 x 2100 크기로 이동하면 괜찮은 성능이 나타납니다.