1805 - 高斯的隱藏 FFT（提早 160 年出土的兇器）#

案件摘要#

1805 年，高斯 (Carl Friedrich Gauss) 在一份從未發表的小行星插值手稿中，發明了一個把 \(N\) 點離散傅立葉轉換從 \(O(N^2)\) 降到 \(O(N\log N)\) 的技巧—— 與 1965 年 Cooley–Tukey 的 FFT（見「1965-FFT快速傅立葉轉換」）核心完全相同，早了 160 年。 可惜高斯只用拉丁文記載、從未宣傳，這把「兇器」塵封於手稿中，直到 Heideman、Johnson 與 Burrus 於 1984 年翻案才重見天日。

前因 -- 為什麼會有這個案子#

• 小行星計算的實際需求：1801 年高斯以極少量觀測數據算出穀神星 (Ceres) 軌道，聲名大噪。軌道與插值計算需要大量三角插值。
• 三角插值 = 離散傅立葉轉換：對 \(N\) 個等距樣本 \(x_j\) 求三角多項式插值，等價於計算

直接計算是 \(N\times N\) 次乘加—— \(N\) 大時計算量爆炸。 - 高斯的偵探直覺：與其蠻力硬算，不如尋找對稱性。

線索與推理 -- 數學式、程式、理論#

分而治之：偶奇拆分#

把求和按 \(j\) 的奇偶拆成兩半，記 \(x_{2m}\) （偶）、 \(x_{2m+1}\) （奇），並利用 \(e^{-2\pi i\, 2m\,k/N} = e^{-2\pi i\, mk/(N/2)}\) ：

\(E_k, O_k\) 是兩個 \(N/2\) 點的 DFT，且週期為 \(N/2\) ，故

兩個 \(N/2\) 點 DFT 產生全部 \(N\) 個輸出——遞迴下去：

撲朔迷離的命案疑點：為何沒有影響？#

• 高斯的手稿用拉丁文寫成，記法與現代訊號處理語言完全不同，無人看得懂其通用性。
• 他只當作小行星插值的「計算技巧」，未發表於期刊、未命名、未宣傳。
• 19 世紀手工計算時代， \(O(N^2)\) 雖慢但還算可行——計算量尚未成為謀殺動機。
• 直到 1960 年代電腦與數位訊號處理興起， \(O(N^2)\) 成為真正的瓶頸，Cooley–Tukey 獨立重新「破案」，一夕成名。

Python 驗證：遞迴 FFT 與蠻力 DFT 比對#

import numpy as np

def dft(x):
    N = len(x)
    return np.array([sum(x[j]*np.exp(-2j*np.pi*j*k/N) for j in range(N))
                     for k in range(N)])          # O(N^2)

def fft_gauss(x):
    N = len(x)
    if N == 1: return x.copy()
    E = fft_gauss(x[0::2]); O = fft_gauss(x[1::2])
    w = np.exp(-2j*np.pi*np.arange(N//2)/N)
    return np.concatenate([E + w*O, E - w*O])    # O(N log N)

x = np.random.randn(256)
print(np.allclose(dft(x), fft_gauss(x)))   # True

結案 -- 後果與影響#

• 歷史改寫：FFT 不是 1965 年的新發明，而是 1805 年已被高斯發明卻塵封的技巧。
• 教訓：發明若未發表、未命名、未迎合時代需求，等於不存在。科學史的功勞屬於「把正確的答案帶到正確的時代」的人。
• Cooley–Tukey 版本因配合數位電腦時代而引爆訊號處理革命（見「1965-FFT快速傅立葉轉換」）。
• 高斯本人早已憑穀神星軌道名滿天下——他不需要這個功勞，但數學史需要等 160 年才能領回它。

關鍵人物與文獻#

• Carl Friedrich Gauss：未發表手稿〈關於插值方法的補充〉(1805)，收錄於 Werke, Bd. 3。
• Heideman, Johnson, Burrus：〈Gauss and the history of the FFT〉, IEEE ASSP Magazine 1, 14 (1984)——翻案文獻。
• 相關案件：1807-Fourier熱傳導論文.md、1965-FFT快速傅立葉轉換.md。