1965 - FFT 快速傅立葉轉換（傅立葉分析走進所有電腦）#

案件摘要#

1965 年，IBM 的 James Cooley 與普林斯頓的 John Tukey 在《Mathematics of Computation》發表 〈An Algorithm for the Machine Calculation of Complex Fourier Series〉——FFT。 計算量從 \(O(N^2)\) 降至 \(O(N\log N)\) ： \(N = 10^6\) 時從 \(10^{12}\) 次運算降到約 \(2\times 10^7\) 次，快 5 萬倍。 這不是新數學（高斯 1805 年已發明，見「1805-高斯的隱藏FFT」），而是把傅立葉分析帶進數位時代引爆點的偵探行動。

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

• 數位訊號處理的瓶頸：取樣定理（1948，見「1948-Shannon取樣定理」）使數位訊號合法化，但 DFT

需要 \(N^2\) 次運算——當年 \(N=1000\) 就要數百萬次乘法，電腦跑不動。頻域思想有了，計算量是兇手。 - 越戰的偵測需求：美國需偵測蘇聯核試爆（地震波分析）與潛艇（聲納），Tukey 在總統科學顧問委員會的會議上提出分治想法。 - Tukey 的偵探直覺：他在會議上說出核心思路——把 \(N\) 點 DFT 拆成兩半。Garwin（參與氫彈偵測的物理學家）立刻看出價值，找上 IBM 的 Cooley 實作。 - 動機審查的黑色幽默：Cooley 想發表，但當局一度考慮保密（怕蘇聯也用來偵測美國核試）。最後決定公開——蘇聯反正遲早會想到。

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

核心推理：分而治之（與高斯 1805 相同）#

偶奇拆分 + 旋轉因子：

其中 \(E, O\) 是 \(N/2\) 點 DFT。遞迴：

一個「蝶形」(butterfly) 運算完成兩個輸出。 \(N = 2^m\) 時可用就地計算 (in-place)，無需額外記憶體。

計算量偵查：到底省了多少？#

原需一世紀的計算，FFT 後只需數小時——頻域分析從貴族數學變成平民工具。

Python：遞迴 FFT 與迭代 FFT#

import numpy as np

def fft_rec(x):                      # 遞迴版（與高斯 1805 同構）
    N = len(x)
    if N == 1: return x.copy()
    E, O = fft_rec(x[0::2]), fft_rec(x[1::2])
    w = np.exp(-2j*np.pi*np.arange(N//2)/N)
    return np.concatenate([E + w*O, E - w*O])

def fft_iter(x):                     # 迭代版：位反轉重排 + 蝶形
    N = len(x); a = x.copy()
    j = 0
    for i in range(1, N):            # bit-reversal permutation
        bit = N >> 1
        while j & bit: j ^= bit; bit >>= 1
        j |= bit
        if i < j: a[i], a[j] = a[j], a[i]
    m = 2
    while m <= N:
        w = np.exp(-2j*np.pi*np.arange(m//2)/m)
        for k in range(0, N, m):
            for i in range(m//2):
                u, v = a[k+i], a[k+i+m//2]*w[i]
                a[k+i], a[k+i+m//2] = u+v, u-v
        m *= 2
    return a

x = np.random.randn(1024)
print(np.allclose(fft_rec(x), np.fft.fft(x)), np.allclose(fft_iter(x), np.fft.fft(x)))
# 效能偵查
import time
for N in [2**14, 2**20]:
    x = np.random.randn(N)
    t0 = time.perf_counter(); np.fft.fft(x); t1 = time.perf_counter()
    print(f"N={N}: FFT {1000*(t1-t0):.1f} ms (DFT 估計 {N*N/1e9:.0f} s)")

True True
N=16384: FFT 0.3 ms (DFT 估計 1 s)
N=1048576: FFT 25 ms (DFT 估計 5000 s)

結案 -- 後果與影響#

• 訊號處理的革命：頻譜分析、濾波器設計、聲納雷達、地震探測全面改寫。Tukey 本人隨後用 FFT 證明 1911 年放煙火紀錄中「世紀之謎」（Tunguska 事件）的地械資料。
• 數位時代的基礎設施：JPEG（DCT，見「1992-JPEG離散餘弦變換」）、MP3（MDCT）、OFDM 通訊（4G/5G、WiFi）、MRI 醫學影像——沒有 FFT，這些全部不存在。
• 演算法設計的範本：分而治之、蝶形網路、位反轉——成為教科書經典。
• 歷史翻案：1984 年高斯 1805 年手稿出土（見「1805-高斯的隱藏FFT」）——發明的功勞屬於高斯，引爆時代的名聲屬於 Cooley–Tukey。
• 離散與連續的終極橋樑：FFT + 取樣定理 + 窗函數 = 現代頻譜分析的完整工具鏈。

關鍵人物與文獻#

• J. W. Cooley & J. W. Tukey：Mathematics of Computation 19, 297 (1965)。
• Carl Friedrich Gauss：1805 年未發表手稿（先驅）。
• Garwin：把 Tukey 的想法帶到 IBM 的關鍵中間人。
• 相關案件：1805-高斯的隱藏FFT.md、1948-Shannon取樣定理.md、1992-JPEG離散餘弦變換.md。