FFTW——一个用纯c语言写的高效FFT算法库

目录

一、FFTW简介（官网翻译）

二、软件特点（官网翻译）

三、资源信息

四、VS2015下的FFTW库使用

（首先是x86版本）

（然后是x64版本）

五、Qt版本下的移植

---

官网网址：FFTW Home Page

这个已经能正常使用，不会继续研究了，这个FFTW只给预编译版本，没法学习源代码。且商用还需要花钱购买许可。

如果需要我已经移植好的源码，见如下链接：

https://market.m.taobao.com/app/idleFish-F2e/widle-taobao-rax/page-detail?wh_weex=true&wx_navbar_transparent=true&id=599845985611&ut_sk=1.AAhiIP37iQwDANlHHj81FWR6_21407387_1564733167252.Copy.detail.599845985611.1030106470&forceFlush=1

一、FFTW简介（官网翻译）

FFTW(The Fastest Fourier Transform in the West)是一个计算一维或者多维DFT(the discrete Fourier transform)的c程序子库，支持任意输入长度，可以是实数或者复数数据。官方当前版本最新是3.3.8（截至2019年8月1日）。

作者是MIT的博士生Matteo Frigo（wiki：Matteo Frigo - Chessprogramming wiki）

和Steven G. Johnson（wiki:https://en.wikipedia.org/wiki/Steven_G._Johnson，个人主页：Professor Steven G. Johnson）。

          

软件的基准是：工作在各种平台上且效果优于其他典型的FFT软件，与vendor-tuned codes也有得一拼(可能是另一种FFT软件)且FFTW是可移植的，不需修改就能在其他架构上直接使用，而vendor-tuned codes不行。

二、软件特点（官网翻译）

1.速度快；
2.支持一维和多维变换；
3.支持任意输入长度变换；
4.纯实数输入输出时能快速变换；
5.支持实数奇偶输入数据变换（不太懂）；he discrete cosine transform (DCT) and the discrete sine transform (DST)
6.高效处理多个或者多步变换，如一次性处理多个需要变换的数据列，变换多维数据的某一维，变换多部分向量的某一部分；
7.并行变换，只对支持多线程的机器有效；
8.对使用C编译器的平台都是可移植的；
9.开源协议为：GPL。

PS：这个开源的软件没有开源源码，只有预编译版本的文件。也就是只能用，不能学习。且如果商用的话，还得花钱买许可。有点背离我使用它的初衷了，这里将VS2015下使用以及QT中使用的方法写出来，然后果断换一个有源码的库。

三、资源信息

说明文档：http://www.fftw.org/fftw3.pdf
问题和回答：FFTW Frequently Asked Questions with Answers
和其他FFT算法的速度比较：FFT Benchmark Results。点击机器型号就能看到在该机器下的算法速度比较；
和其他FFT算法的准确度比较：FFT Accuracy Benchmark Results
对作者的采访：RCE 73: FFTW - Fastest Fourier Transform in the West | Podcast | rce  

访谈在b站：爱剪辑-FFTW作者访谈_哔哩哔哩_bilibili

下载页面：FFTW Download Page

四、VS2015下的FFTW库使用

这个fftw库在windows下的编译真的好复杂，老是出错。这里介绍一下成功在vs2015中编译x86和x64平台测试成功的经验，以及使用qt平台编译成功的经验

（首先是x86版本）

1.下载32位的预编译代码并解压该zip文件

2.使用vs2015的x86命令提示操作生成lib文件

lib文件有三种精度的，这里我们把它全部生成出来

3.拷贝3种精度的dll文件到C:\Windows\SysWOW64下

4.新建vs2015的c++工程

5.将解压并生成了lib文件的文件夹拷贝到工程目录下

6.导入头文件fftw3.h并新建测试代码

测试代码如下：

#pragma comment(lib, "D:\\qt4.8.0\\userfile\\cplusfile\\Project3\\fftw-3.3.5-dll32\\libfftw3-3.lib")
#pragma comment(lib, "D:\\qt4.8.0\\userfile\\cplusfile\\Project3\\fftw-3.3.5-dll32\\libfftw3f-3.lib")
#pragma comment(lib, "D:\\qt4.8.0\\userfile\\cplusfile\\Project3\\fftw-3.3.5-dll32\\libfftw3l-3.lib")
#include <stdio.h>
#include <stdlib.h>
#include <fftw3.h>
#define N 5
int main()
{
	fftw_complex *in, *out;
	fftw_plan p;
	in = (fftw_complex*)fftw_malloc(sizeof(fftw_complex) * N);
	out = (fftw_complex*)fftw_malloc(sizeof(fftw_complex) * N);
	p = fftw_plan_dft_1d(N, in, out, FFTW_FORWARD, FFTW_ESTIMATE);
 
	int n;
	for (n = 0; n < N; n++)
	{
		in[n][0] = 1;
		in[n][1] = 2;
	}
 
	fftw_execute(p);
	fftw_destroy_plan(p);
 
	for (n = 0; n < N; n++)
	{
		printf("%3.2lf+%3.2lfi    ", out[n][0], out[n][1]);
	}
	printf("\n");
	fftw_free(in); fftw_free(out);
	system("pause");
	return 0;
}

7.进行lib文件的路径设置

8.当你自己使用时，需要改lib文件的路径

9.最终运行成功的标志

（然后是x64版本）

区别1：下载并使用64位的zip文件。

区别2：使用vs2015的x64命令提示符工具生成lib文件

区别3：vs2015的工程需要使用x64平台，然后修改lib文件路径

其他的同x86平台下的操作。

五、Qt版本下的移植

我使用的qt版本如下：

昨天加今天上午一直搞不好，结果自从使用vs2015成功移植32位的fftw库后，下午非常快地成功了。前期对于下载的x64zip文件的处理都是相同的，主要是需要在qt中添加dll和lib文件。

1.下载x64fftw的zip文件并解压，然后与前面使用vs2015添加x64的fftw库一样生成lib文件

生成的指令需要指定位x64的机器，如下：

lib /machine:x64 /def:libfftw3-3.def
lib /machine:x64 /def:libfftw3f-3.def
lib /machine:x64 /def:libfftw3l-3.def

2.新建一个qt的纯c++项目

需要注意的是，选择Mingw，而非msvc2015（我还没测试过）。

3.将下载解压以及生成了lib文件的的fftw库文件夹拷贝到工程目录下，并导入头文件fftw3.h

4.将dll文件拷贝到C:\Windows\System32

lib文件和dll文件都是需要的，如果不放在该目录下，也需要在pro中指示dll文件路径

或者在工程的debug目录下放dll文件

5.编写测试代码

#include <iostream>
#include "fftw-3.3.5-dll64/fftw3.h"
#include <stdlib.h>
#include <stdio.h>
#define N 5
 
using namespace std;
 
int main()
{
    fftw_complex *in, *out;
    fftw_plan p;
    in = (fftw_complex*)fftw_malloc(sizeof(fftw_complex) * N);
    out = (fftw_complex*)fftw_malloc(sizeof(fftw_complex) * N);
    p = fftw_plan_dft_1d(N, in, out, FFTW_FORWARD, FFTW_ESTIMATE);
 
    int n;
    for (n = 0; n < N; n++)
    {
        in[n][0] = 1;
        in[n][1] = 2;
    }
 
    fftw_execute(p);
    fftw_destroy_plan(p);
 
    for (n = 0; n < N; n++)
    {
        printf("%3.2lf+%3.2lfi    ", out[n][0], out[n][1]);
    }
    printf("\n");
    fftw_free(in);
    fftw_free(out);
 
    return 0;
}

6.在pro文件中添加lib库

7.运行的结果如下图说明成功