透過求值相乘
令 為整數,寫 、;零多項式可用一項的列 表示。其乘積的係數為
直接對所有係數對求和需 次算術操作。另一方法是在選定點上分別求值、逐點相乘,再恢復係數。單位根可讓這些求值共用工作。我們先使用精確複數算術;實際浮點表現是另一個問題。
選擇二的冪 ,在兩個係數列末端補零至長度 。
定義 10.1.1
(離散 Fourier 變換)
令 ,它是本原 次單位根。對長度為 的列 ,離散 Fourier 變換定義為
這些是多項式 在 的值。我們採用正指數慣例;下方反變換使用相反符號。
反變換與循環卷積
定理 10.1.2
(反變換公式)
對每個長度為 的列 ,
證明
(消失的等比和)
對整數 ,有限等比和滿足
若 ,每一項都是 。否則由 的本原性,公比 不等於一,但其 次方為一,故等比和 為零。把 乘以 並對 求和,得
因為對 ,只有 一項保留下來。
定義 10.1.3
(循環卷積)
對長度為 的列 ,它們的循環卷積是長度為 的列
定理 10.1.4
(逐點乘積給出循環卷積)
若 是 與 的循環卷積,則對每個 都有 。因此對逐點乘積作反變換便返回 。若 是 的係數列並補零至長度 ,則 就是普通乘積的係數,後面接著零。
證明
(指數相加,而且沒有項繞回)
。由於 ,指數只取決於 ,把 的項合併,便得 。再由反變換公式從這些值恢復 。
對補零後的列,當 時 ,當 時 ,所以非零項有 。於是對 , 即 ,故 時 ,更高的位置 。
概念視角結構
循環卷積即模 $x^n$ - 1 的乘法
同一些對象還有第二種描述。 個點 恰是 的全部相異根,而模 時 化為 。所以 與 的循環卷積就是 的係數列,而變換是用這個餘式在 個根上的值來記錄它的映射。值的逐點相乘就是餘式的乘法,反變換公式則說明次數低於 的餘式由這 個值唯一決定。混疊就是取餘式這一步本身:次數達到或超過 的乘積並不等於它的餘式。
因此補零並非可有可無。
反例模式
補零不足會令乘積折疊
一個看似合理的捷徑,是只按輸入長度選 ,再相信反變換會給出普通乘積。取 、,普通乘積為 。 與自身的循環卷積有 及 ,給出列 : 的係數繞回常數位置,亦即 。修正方法是選 ;此處 便能把三個係數分開。
把變換分為偶數與奇數索引
假設 且為二的冪。把係數列分成偶數及奇數索引,定義 和 ,則
由於 是本原 次單位根,遞歸地在其冪上求兩個長度 的列之值,所得變換分別記為 和 。
定理 10.1.5
(基二 FFT)
設 為二的冪,,則
按這些公式遞歸計算變換,當 時 ;若 的冪已提供,或每層以線性工作產生,當 時需 次算術操作。
證明
(對大小作歸納,再解遞推式)
時, 的變換是 。設 、,按索引奇偶拆開定義中的和:
其中兩個內和是以 為根的半長度列之變換,由歸納假設正確。對索引 ,有 ,並因 而 ,由此得第二條公式。
兩個半大小子問題加上 的合併工作,給出 ,其解在 時是 。
證明透視
兩條合併公式依賴甚麼
這個證明用到 的三個性質,各有分工。 是本原 次單位根,使兩個半大小問題與原問題同類,歸納才能進行。等式 令同一對半大小的值只需一次乘以 便產生兩個輸出 與 ,工作量因而減半,這就是對數因子的來源。最後, 須為二的冪,這樣對半分可一直進行到 ,不會剩下奇數大小。反變換重用同一遞歸,因為 也是本原 次單位根,最後再按反變換公式除以 。所以兩次正變換、逐點乘法及一次反變換共需 次算術操作。
四點例題
例題 10.1.6
(用四個點相乘 1 + 2x 與 1 + x + )
取 、。乘積次數最多為三,故 足夠。以 ,在 的求值為:
| 列 | 在 | 在 | 在 | 在 |
|---|---|---|---|---|
| 3 | ||||
| 3 | 1 | |||
| 逐點乘積 | 9 |
把反變換公式套用於最後一行得 ,所以 。例如 的係數為 。乘積次數最多為三,故此長度四的變換不會把非零乘積項折回較低係數。
例題 10.1.7
(對 1 + 2x 的變換作一輪蝶形運算)
把 補零為 ,、。偶數項 與奇數項 以 作大小為二的變換:,。合併得
與上表第一行吻合。兩個半大小的值各被使用兩次,一次用加號,一次用減號。
例題 10.1.8
(補零多於最低要求)
相乘 ,此時 ,。不小於 的最小二的冪是 ,不是 。乘積為 ,所以反變換返回 ,後面有三個零。檢驗:, 的逐點乘積是 ,而輸出係數之和 。多出的零沒有壞處;只有輸出太少才會令各項折疊。
成本與數值限制
算術操作上界把複數加法與乘法視為常數成本。它不是任意大精確係數的位元複雜度界,也不保證浮點算術答案精確。只有另有誤差界保證每個計算出的實部係數距真整數值少於 ,才能據此捨入恢復整數係數;虛部捨入誤差也須處理。精確模數變換或任意精度方法則需要各自的單位根、模數與重構條件。
常見錯誤
常見錯誤
(把正變換用兩次,而不是求反變換)
把正變換公式直接拿來當反變換,既漏掉符號的改變,也漏掉因子 。對 ,列 的變換是 。再套用一次正變換得 ,這是 的索引按模 反轉後再乘以 ,並不是 。應使用 並除以 。
常見錯誤
(以為卷積必須用二的冪)
只要 ,反變換公式與循環卷積定理對每個 都成立。需要二的冪的,只是令變換變快的基二分拆。若 不是二的冪,定義仍然正確;只是上面的遞歸不能照原樣套用。
練習
快速檢查
(對 ,按正指數慣例計算 的變換。)
取 ,使用 。
解答 · 答案
因 ,,所以變換為 。
快速檢查
(解釋為何相乘次數最多一及二的多項式時 足夠,但 不一定足夠。)
數一數乘積有多少個係數。
解答 · 答案
乘積次數最多為 ,即四個係數,而 。若 ,次數為 和 的項會繞回次數 和 。對 ,長度二的循環結果是 ,並非乘積的係數。
快速檢查
(若在四個單位根上的 ,用反變換公式恢復 。哪個係數列有此變換?)
對每個 計算 。
解答 · 答案
時,和為 。 時,它是 的非平凡冪之等比和,等於零。所以 ,即常數多項式 ,它在每個點的值都是 。
快速檢查
(用 的蝶形公式計算 的變換。)
偶數項是 ,奇數項是 。
解答 · 答案
偶數部分的變換是 ;奇數部分 在大小為二時變換為 。以 :、、、。所得列 就是多項式 在四個單位根上的值。