快速傅立葉變換 (FFT) 加速大整數乘法：原理與實作詳解

傳統的大整數乘法採用逐位相乘並累加的方式，時間複雜度為 O(N²)。當處理百萬位數字時，這會帶來嚴重的效能瓶頸。利用 快速傅立葉變換 (FFT)，可將複雜度大幅降低至 O(N log N log log N)，甚至在實作中常視為 O(N log N)，效能提升極為顯著。

核心數學原理：卷積定理

將兩個 N 位十進制整數視為係數向量：

a = (a_N-1...a₁a₀)₁₀ = Σ a_i·10ⁱ

b = (b_N-1...b₁b₀)₁₀ = Σ b_j·10^j

它們的乘積 c = a × b 的係數 c_k 正好是兩向量的 離散卷積：

c_k = Σ a_i·b_k-i (i 從 0 到 k，超出範圍視為 0)

根據 卷積定理：向量卷積的離散傅立葉變換 (DFT) 等於各自 DFT 的逐項乘積。因此計算步驟為：

1. 對 {a_i} 和 {b_j} 分別做 DFT，得 {A_i}、{B_j}。
2. 逐項相乘得到 {C_k = A_k·B_k}。
3. 對 {C_k} 做逆 DFT (IDFT)，得到卷積結果 {c_k}。
4. 對 {c_k} 處理進位，即得最終乘積。

範例演示：678 × 432

取 N=3，補零至長度 8 (2³)：

{a} = {0,0,0,0,0,6,7,8}，{b} = {0,0,0,0,0,4,3,2}

令 ω = e^-2πi/8，計算 DFT 並逐項相乘後再做 IDFT，最終得到卷積向量 {c} = {0,0,0,24,46,65,38,16}，經進位後得 292896，與直接相乘結果一致。

關鍵突破：快速傅立葉變換 (FFT)

直接計算 DFT 複雜度仍為 O(N²)。《關鍵在於：FFT 利用分治策略，將長度 N 的 DFT 分解為兩個長度 N/2 的 DFT，遞歸進行，僅需 O(N log N) 時間。 當 N=10⁶ 時，FFT 僅需秒級，而直接法需數週。

實作注意事項：精度與進制選擇

FFT 使用浮點運算，須防止捨入誤差導致整數位錯誤。雙精度浮點數尾數 53 位，滿足：

2·log₂B + log₂N + 常數·log₂log₂N < 53

因此基數 B 不宜過大。常用 256 進制 (B=256) 或為方便十進制轉換用 100 進制 (B=100)。

總結與展望

本文詳細推導了 FFT 加速大整數乘法的數學基礎、演算法流程、具體數值範例及精度分析。下一篇將提供任意精度整數運算的 C# 完整實作程式碼。