用 FFT 做快速乘法（fast multiplication via the FFT）
/ F-F-T /
用課本方法把兩個大數（或兩個多項式）相乘要 O(n^2)——一邊的每位數乘上另一邊的每位數。當數字有數百萬位時，這實在太慢。用快速傅立葉轉換（fast Fourier transform, FFT）做快速乘法，靠一個漂亮的繞道，以 O(n log n) 完成同一件事：它不逐係數相乘，而是把每個輸入轉成另一種表示法，在那裡乘法變得輕而易舉，乘完再轉回來。
關鍵想法是描述多項式的兩種方式。一個 (n-1) 次多項式可以用它的 n 個係數給出，也可以用它在 n 個選定點上的值（取樣）給出。在係數形式下相乘是昂貴的 O(n^2) 卷積；但在值形式下相乘輕而易舉——要得到乘積在某點的值，你只要把兩個輸入在該點的值相乘，每點一次乘法，總共 O(n)。所以計畫是：(1) 在一組巧妙選定的 2n 個點上求兩個多項式的值，(2) 把兩串值逐點相乘，O(n)，(3) 內插回去以還原乘積的係數。神奇之處在於，FFT 在特別選定的點（複數單位根）上以 O(n log n) 而非 O(n^2) 完成求值，其反轉換也同樣快地完成內插。大整數的處理方式是把其位數區塊當成多項式係數、再把多項式相乘。一個常見且精確的變體稱為 NTT（數論轉換），把這一切改在模算術裡做而非用複數，完全避開浮點捨入。
這把乘法壓到 O(n log n)，是個戲劇性的改進，驅動了大整數函式庫、多項式算術、訊號處理，以及可化為卷積的字串演算法。誠實的提醒在實務上很重要。第一，常數因子很大，所以對小輸入，課本的 O(n^2) 或卡拉楚巴的 O(n^1.585) 其實更快——FFT 只有在 n 夠大時才勝出。第二，複數 FFT 會累積浮點誤差，所以要得到精確整數結果，你要嘛用足夠的精度，要嘛改用 NTT。（本條聚焦於把 FFT 當成乘法工具；FFT 本身的分治推導另在分治法欄目中說明。）
把 (1 + 2x) 乘以 (3 + 4x)。係數法：3 + 4x + 6x + 8x^2 = 3 + 10x + 8x^2，O(n^2)。FFT 法：在足夠多點上取兩者的樣本，把樣本值逐點相乘（O(n)），再內插回去得到係數 3、10、8——同一答案，但對大次數而言，求值／內插步驟跑 O(n log n)。
求值、逐點相乘、內插：O(n log n) 取代了 O(n^2) 的課本卷積。
FFT 乘法只在 n 大時勝出：其常數因子很大，所以小輸入時課本法或卡拉楚巴更快，而複數 FFT 版本要得到精確整數結果需小心處理（或改用 NTT）。