普林斯敦的數學教授 John Tukey FFT (快速傅立葉轉換)

 

李中志

不少人說 FFT (快速傅立葉轉換) 是所有算法中最重要的一個，我不是很同意，但在CS以外領域可能不假。別說通訊，影像的壓縮也用到。連我一直唱衰的量子計算，我也得承認量子電腦的確可以再助 FFT 一臂之力，叫 QFT，雖然離實用還遠，但算法上已證可行，這是量子計算少數不唬爛的例子。

FFT 在1963年由一個普林斯敦的數學教授 John Tukey 向甘迺迪解釋，他是總統的科學顧問。甘迺迪應該是有聽沒有到，一旁的 IBM工程師 Dick Garwin 也在想一樣的問題，回去後立刻叫程式員 John Cooley 寫 code. Cooley 催促 Tukey 發表，但 Tukey 沒有興趣，當時算法還不算門嚴謹的學科，普林斯敦的大教授認為那只是個簡單的觀察，別人可能早就發現了，不值得發表。Cooley 只好幫他寫，掛共同作者，這篇演算法史上最重要的論文之一就這樣在1965年發表了。

其實 Tukey 並沒有說錯，那只是個簡單的觀察，30年代一個英國工程師也以同樣的方法用紙筆計算。FFT 若能早10年在50年代初發表，世界的核武可能減少一大半，因為 FFT 能迅速算出偵測到的地下核爆震波，讓防止核武競賽的公約可以落實監控。其實更早100多年，高斯早就發現 FFT 了，只是沒發表，用拉丁文寫在稿紙上。唉，高斯這人真的很討厭，每個做數學的在高斯面前都是庸才。

FFT 的故事很有趣，google 一下可以找到很多，YT 有不錯的影片解說。

我不解的是，多數給大學部學生的算法教科書不是沒提FFT，就是放到最後面，沒時間教。其實 FFT 的算法不難，比較吃力的部分是數學，用到虛數，但大二學生剛修完微積分或線性代數，反而比 CS 的研究生更記得那些東西，何況數學部分懂就懂了，而程式技巧也只是典型的 Divide and Conquer。我教算法時一定會插入 FFT，不管教科書有沒有，若非社區大學的轉學生，我覺得學生還頗能掌握，而且能適時拉回學生對數學的重視。建議教算法的老師不要跳過 FFT。