fft程序(fft算法c語言實(shí)現(xiàn)詳解)
從Fortran到arXiv.org,計(jì)算機(jī)程序和平臺(tái)的進(jìn)步,令生物學(xué)、氣候科學(xué)與物理學(xué)突飛猛進(jìn)。
在2019年,事件視界望遠(yuǎn)鏡向世界首次揭開了黑洞的神秘面紗。但我們看到的那個(gè)發(fā)光環(huán)形黑洞圖像并不是直接拍攝得到的,而是利用來自于美國、墨西哥、智利、西班牙和南極的射電望遠(yuǎn)鏡所捕獲的數(shù)據(jù),通過復(fù)雜的數(shù)學(xué)變換和計(jì)算處理而得到的[1]。在發(fā)布結(jié)果的同時(shí),該團(tuán)隊(duì)也公開了實(shí)現(xiàn)這一突破性成就的代碼,使得科學(xué)界詳細(xì)理解其實(shí)現(xiàn)過程,并以此為基礎(chǔ)更深入地研究。
從天文學(xué)到動(dòng)物學(xué),這樣的研究模式在各個(gè)學(xué)科中越來越趨于普遍:在現(xiàn)代每一項(xiàng)重大科學(xué)發(fā)現(xiàn)的背后,總有計(jì)算機(jī)的身影。加州斯坦福大學(xué)的計(jì)算生物學(xué)家Michael Levitt由于在化學(xué)結(jié)構(gòu)建模的計(jì)算策略方面做出的杰出貢獻(xiàn)而分享了2013年的諾貝爾化學(xué)獎(jiǎng),他提及自己在1967年剛開始這項(xiàng)工作時(shí),實(shí)驗(yàn)室電腦的內(nèi)存和計(jì)算性能只有不到現(xiàn)在筆記本電腦的萬分之一。他說:「雖然我們現(xiàn)在已經(jīng)掌握了強(qiáng)大的計(jì)算資源,但思考的重要性并沒有絲毫減弱。」
這就需要科學(xué)家兼程序員。如果沒有可以處理研究問題的軟件,沒有知道如何編寫并使用程序的研究人員,再強(qiáng)大的電腦也會(huì)顯得毫無用處。Neil Chue Hong是總部位于英國愛丁堡的軟件可持續(xù)性研究所的負(fù)責(zé)人,該研究所主要致力于持續(xù)改善科學(xué)軟件的研發(fā)和使用,Neil說:「現(xiàn)在的科學(xué)研究基本都會(huì)運(yùn)用軟件來進(jìn)行,它們已經(jīng)滲透到了研究的方方面面?!?/p>
插圖: Pawe? Jońca
科學(xué)發(fā)現(xiàn)理應(yīng)是媒體的頭版頭條。但本期《自然》中,我們想要和讀者一起聊聊這些發(fā)現(xiàn)背后的故事,一起回顧過去幾十年來極大地改變研究進(jìn)程的關(guān)鍵代碼。
盡管這樣的列表并非絕對(duì),但在過去一年里我們調(diào)研了大量研究人員,匯總了不同領(lǐng)域內(nèi)對(duì)科研帶來巨大影響的的十大軟件工具。
編程語言先驅(qū)者:Fortran編譯器
(1957)
第一臺(tái)現(xiàn)代電子計(jì)算機(jī)對(duì)于用戶并不友好。編程需要通過手動(dòng)逐個(gè)鏈接電路來完成。雖然隨后的機(jī)器語言和匯編語言迅速發(fā)展,可以讓用戶通過代碼進(jìn)行編程,但依然需要對(duì)計(jì)算機(jī)體系結(jié)構(gòu)有著深入的理解,這阻礙了許多科學(xué)家使用計(jì)算機(jī)的效率。
隨著20世紀(jì)50年代符號(hào)化語言的發(fā)展,效率慢慢提高,尤其是「公式翻譯」語言Fortran的出現(xiàn)改變了這一局面。Fortran語言是由John Backus與其在加州圣何塞的IBM團(tuán)隊(duì)開發(fā)的。用戶可以利用Fortran中人類可讀的指令來編程,例如編寫x=3+5的計(jì)算公式,隨后編譯器就可以將其轉(zhuǎn)化為快速高效的機(jī)器代碼。
CDC 3600計(jì)算機(jī)于1963年送達(dá)位于科羅拉多州博爾德的國家大氣研究中心,它可以在Fortran編譯器幫助下進(jìn)行編程
但編程仍然不是一件容易的事情:早期的程序員使用打孔卡來輸入代碼,稍微復(fù)雜點(diǎn)的模擬就需要上萬張打孔卡來編寫程序。但新澤西普林斯頓大學(xué)的氣候?qū)W家Syukuro Manabe表示,F(xiàn)ortran為非計(jì)算機(jī)科學(xué)家的研究者提供了一種高效的編程手段?!肝覀兊谝淮慰梢宰约簩?duì)計(jì)算機(jī)進(jìn)行編程」,Manabe說。他和同事們利用Fortran開發(fā)了第一個(gè)成功的氣候模型。
如今,F(xiàn)ortran已經(jīng)進(jìn)入了第八個(gè)十年,它依舊廣泛應(yīng)用于氣象建模、流體力學(xué)、計(jì)算化學(xué)和其他需要復(fù)雜線性代數(shù)與強(qiáng)大計(jì)算能力的學(xué)科。其生成的代碼運(yùn)算高效,依然有很大比例的程序員會(huì)使用Fortran。中古Fortran代碼庫仍然活躍在全球各地的超級(jí)計(jì)算機(jī)和實(shí)驗(yàn)室中。「以前的程序員清楚自己在做什么」加州蒙特雷海軍研究生院的應(yīng)用數(shù)學(xué)家和氣候建模專家Frank Giraldo說,「他們非常注重內(nèi)存,因?yàn)橐郧暗膬?nèi)存非常小?!?/p>
信號(hào)處理器:快速傅立葉變換
(1965)
當(dāng)射電天文學(xué)家掃視天空時(shí),他們會(huì)捕獲到一系列隨時(shí)間變化的復(fù)雜信號(hào)。為了理解這些電波的本質(zhì),他們需要看到這些信號(hào)轉(zhuǎn)成頻率方程是什么樣的。研究人員可以使用一種被稱為傅立葉變換的數(shù)學(xué)過程來完成這一過程,問題在于它的效率很低,一個(gè)N大小的數(shù)據(jù)集需要N2的計(jì)算量。
但在1965年,美國數(shù)學(xué)家JamesCooley和John Tukey發(fā)明了一種方法來加速這一過程。使用遞歸,一種「分而治之」的編程手段(算法可以重復(fù)調(diào)用自身),快速傅立葉變換(FFT)可以將傅立葉變換的計(jì)算降低到Nlog2(N)步。計(jì)算速度隨著數(shù)據(jù)集的增大而增加,1000個(gè)數(shù)據(jù)點(diǎn)的情況下速度提升100倍,而對(duì)于一百萬個(gè)點(diǎn)的情況則可以提速5萬倍。
英國牛津大學(xué)的數(shù)學(xué)家Nick Trefethen說,這其實(shí)是一次重復(fù)發(fā)現(xiàn)——德國數(shù)學(xué)家高斯(Carl Friedrich Gauss)在1805年曾提出過這個(gè)算法,但他并未發(fā)表。然而,Cooley和Tukey為數(shù)字信號(hào)處理、圖像分析、結(jié)構(gòu)生物學(xué)等等領(lǐng)域打開了廣闊的應(yīng)用空間。Trefethen說:「這確實(shí)是應(yīng)用數(shù)學(xué)和工程領(lǐng)域的重大事件?!?FFT已經(jīng)在代碼中實(shí)現(xiàn)了很多次,最為著名的是FFTW(西方最快的傅立葉變換)。
作者:yunbaotang本文地址:http://www.ntlljf.com/bao/36563.html發(fā)布于 2023-08-24
文章轉(zhuǎn)載或復(fù)制請(qǐng)以超鏈接形式并注明出處孕寶堂

