用 FFT 做多項式乘法（polynomial multiplication by FFT）

手算兩個多項式相乘，就是對它們的係數列表做卷積：一個的每個係數乘上另一個的每個係數，加進正確的輸出格——對 n 次多項式約 n^2 次乘法。FFT 透過切換表示法給出更快的路徑：當多項式以值（而非係數）形式給出時，相乘便宜得多。

這個策略有三個動作，並建立在一個事實上：在值形式中，乘法是平凡的——若 P 與 Q 在同一組點上有值 p_i 與 q_i，則它們的乘積 P*Q 在每個點的值就是 p_i * q_i，純粹是逐點相乘。所以：(1) 用 FFT 在 2n 個單位根上評估兩個多項式，以 O(n log n) 把係數轉成值；(2) 以 O(n) 把兩個值列表逐點相乘；(3) 用反 FFT 把乘積的值內插回係數，O(n log n)。總時間 O(n log n)，相對 O(n^2) 的課本卷積是巨大勝利。你在 2n 個點上評估而非 n 個，是因為乘積的次數可達 2n-2，需要這麼多值才能唯一確定。

這是計算卷積的標準快速法，而卷積到處可見：大整數相乘（把位數寫成多項式係數）、訊號濾波、用生成函數計數、以及帶萬用字元的字串比對。這正是 FFT 應出現在演算法課程中的具體理由。同樣的告誡適用：把係數陣列補齊使工作長度為 2 的冪，並記住複數運算的捨入——對精確的大整數乘積，把最後的係數四捨五入到最近整數，或用數論轉換以保持精確。