fft程序(fft算法c语言实现详解)

9790 127 0

从Fortran到arXiv.org,计算机程序和平台的进步,令生物学、气候科学与物理学突飞猛进。

在2019年,事件视界望远镜向世界首次揭开了黑洞的神秘面纱。但我们看到的那个发光环形黑洞图像并不是直接拍摄得到的,而是利用来自于美国、墨西哥、智利、西班牙和南极的射电望远镜所捕获的数据,通过复杂的数学变换和计算处理而得到的[1]。在发布结果的同时,该团队也公开了实现这一突破性成就的代码,使得科学界详细理解其实现过程,并以此为基础更深入地研究。

从天文学到动物学,这样的研究模式在各个学科中越来越趋于普遍:在现代每一项重大科学发现的背后,总有计算机的身影。加州斯坦福大学的计算生物学家Michael Levitt由于在化学结构建模的计算策略方面做出的杰出贡献而分享了2013年的诺贝尔化学奖,他提及自己在1967年刚开始这项工作时,实验室电脑的内存和计算性能只有不到现在笔记本电脑的万分之一。他说:「虽然我们现在已经掌握了强大的计算资源,但思考的重要性并没有丝毫减弱。」

这就需要科学家兼程序员。如果没有可以处理研究问题的软件,没有知道如何编写并使用程序的研究人员,再强大的电脑也会显得毫无用处。Neil Chue Hong是总部位于英国爱丁堡的软件可持续性研究所的负责人,该研究所主要致力于持续改善科学软件的研发和使用,Neil说:「现在的科学研究基本都会运用软件来进行,它们已经渗透到了研究的方方面面。」

 

插图: Paweł Jońca

科学发现理应是媒体的头版头条。但本期《自然》中,我们想要和读者一起聊聊这些发现背后的故事,一起回顾过去几十年来极大地改变研究进程的关键代码。

尽管这样的列表并非绝对,但在过去一年里我们调研了大量研究人员,汇总了不同领域内对科研带来巨大影响的的十大软件工具。

编程语言先驱者:Fortran编译器

(1957)

第一台现代电子计算机对于用户并不友好。编程需要通过手动逐个链接电路来完成。虽然随后的机器语言和汇编语言迅速发展,可以让用户通过代码进行编程,但依然需要对计算机体系结构有着深入的理解,这阻碍了许多科学家使用计算机的效率。

随着20世纪50年代符号化语言的发展,效率慢慢提高,尤其是「公式翻译」语言Fortran的出现改变了这一局面。Fortran语言是由John Backus与其在加州圣何塞的IBM团队开发的。用户可以利用Fortran中人类可读的指令来编程,例如编写x=3+5的计算公式,随后编译器就可以将其转化为快速高效的机器代码。

 

CDC 3600计算机于1963年送达位于科罗拉多州博尔德的国家大气研究中心,它可以在Fortran编译器帮助下进行编程

但编程仍然不是一件容易的事情:早期的程序员使用打孔卡来输入代码,稍微复杂点的模拟就需要上万张打孔卡来编写程序。但新泽西普林斯顿大学的气候学家Syukuro Manabe表示,Fortran为非计算机科学家的研究者提供了一种高效的编程手段。「我们第一次可以自己对计算机进行编程」,Manabe说。他和同事们利用Fortran开发了第一个成功的气候模型。

如今,Fortran已经进入了第八个十年,它依旧广泛应用于气象建模、流体力学、计算化学和其他需要复杂线性代数与强大计算能力的学科。其生成的代码运算高效,依然有很大比例的程序员会使用Fortran。中古Fortran代码库仍然活跃在全球各地的超级计算机和实验室中。「以前的程序员清楚自己在做什么」加州蒙特雷海军研究生院的应用数学家和气候建模专家Frank Giraldo说,「他们非常注重内存,因为以前的内存非常小。」

信号处理器:快速傅立叶变换

 (1965)

当射电天文学家扫视天空时,他们会捕获到一系列随时间变化的复杂信号。为了理解这些电波的本质,他们需要看到这些信号转成频率方程是什么样的。研究人员可以使用一种被称为傅立叶变换的数学过程来完成这一过程,问题在于它的效率很低,一个N大小的数据集需要N2的计算量。

但在1965年,美国数学家JamesCooley和John Tukey发明了一种方法来加速这一过程。使用递归,一种「分而治之」的编程手段(算法可以重复调用自身),快速傅立叶变换(FFT)可以将傅立叶变换的计算降低到Nlog2(N)步。计算速度随着数据集的增大而增加,1000个数据点的情况下速度提升100倍,而对于一百万个点的情况则可以提速5万倍。

英国牛津大学的数学家Nick Trefethen说,这其实是一次重复发现——德国数学家高斯(Carl Friedrich Gauss)在1805年曾提出过这个算法,但他并未发表。然而,Cooley和Tukey为数字信号处理、图像分析、结构生物学等等领域打开了广阔的应用空间。Trefethen说:「这确实是应用数学和工程领域的重大事件。」 FFT已经在代码中实现了很多次,最为著名的是FFTW(西方最快的傅立叶变换)。