c++ - C++ 中的 fftw 对于 2 的幂变慢？

Question

我正在使用 C++ 中的 fftw 库。我知道 fft 的计算对于 2 的幂是最有效的，但我创建了一个二维 fft 的最小示例，但得到了不同的结果。没有 2 次方的 2d-fft 计算速度比另一个快得多。这是我的代码:

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);

我为 N 和 M 选择了质数。我的程序返回:对于 signala(非 2 的幂):2.95 秒对于 signala_ext(2 的幂):5.232 秒

为什么 2 的幂的 fft 这么慢？我做错了什么？

如有任何帮助，我将不胜感激!

Answer 1

FFTW 喜欢小素数幂乘积的维度。满足此条件的大于 2083 或 2087 的最接近值是 2100(2100 = 2² * 3 * 5² * 7)，因此如果您选择 2100 x 的尺寸2100 那么你应该会看到不错的性能。