使用傅立葉轉換計算多項式乘法(一)

陳奕熹
陳奕熹
Jan 11 · 7 min read

大數下快速運算

最近 jserv 課堂上提到 Using Fourier Transforms To Multiply Numbers — Interactive Examples 這篇昨天(01/10)寫的奇異文章,雖然我工程數學學很爛(印象中一直在背證明XDDD),但是難得傅立葉轉換出了一個我比較能夠理解的應用場景,就來研究一下

感謝 miskcoo 在 2015 年寫的从多项式乘法到快速傅里叶变换提供中文方面的參照,同時也讓我複習基本的工程數學


為什麼需要使用到傅立葉轉換?

首先,我們需要知道 「為什麼明明是簡單的多項式乘法卻要用到數學轉換?」

原本的多項式乘法在項數/ 係數極大的狀況下需要大量的中間項運算,需要花費大量時間得到一個精確值

今天透過傅立葉轉換,把原本以多項式係數表示的方程式改以點表示法,因為點表示法上的運算數量較少,所以能夠在大數上得到一定的效能提昇

整體架構

在理解整體架構前,我們需要具備一些數學基礎知識

多項式的係數表示法(coefficient representation)

一個多項式有兩種方法表示,一種是透過將係數組成 n 維向量,以形成「係數表示法」,這種表示法對同一個方程式來說是唯一的

多項式的點表示法(point-value representation)

另外一種表示法是「點表示法」,事實上就是透過 n+1 個點描述 n 次方的方程式,感覺上可以理解我們國高中描點畫數線的過程; 這種描述方法對同一個方程式來說不唯一,但是每個點表示法明確對應一個方程式

圖取自从多项式乘法到快速傅里叶变换

這個就是簡單的架構圖了,可以看到原本在係數表示法時運算複雜度為 O(n ^ 2),因為 A(x) 與 B(x) 都需要 traverse 一次

透過傅立葉轉換/反轉換(其實精確來說是快速傅立葉轉換/反轉換)以 O(n log n)的成本把原本係數表示法轉換成點表示法,因為在點表示法上我們只需要用 n+1 個點就能夠表示一個 n 次方多項式,因此運算複雜度大大降低到 O(n)

什麼是傅立葉轉換?

傅立葉轉換在電機領域中,被大量用在時域與頻域之間的轉換, jserv 老師針對傅立葉轉換寫了一篇平易的圖解傅立葉分析

不過這邊用到的是快速傅立葉轉換 / 反轉換,根據維基百科的定義,他是一種「快速计算序列的离散傅里叶变换(DFT)或其逆变换的方法」,類似的想法也可以想到「類比轉數位」只取樣部份資料點將連續資料簡化成不連續的離散資料

以快速傅立葉常見的 Cooley-Tukey 算法為例,他是一種 divide and conquer 的算法(所以時間複雜度才會跑出 log n)

假設今天有一個 n-1 次方的方程式 A(x),這邊假設 n = 2 的 m 次方 - 1,其中 m 為整數

這邊同時需要用到複數概念中的單位根, n 次單位根代表能夠滿足 Z ^ n = 1的方程式解,上面這個算是就是單位根的算術表示

快速傅立葉轉換

Cooley-Tukey 算法需要我們把這些單位根帶入方程式 A(x) 求對應的點,令 n 個 n 次方根為 Wn,這樣把係數表示式轉換成點表示式又被叫做離散傅立葉轉換(Discrete Fourier Transform, DFT)

到這邊為止,所需要的時間複雜度還是 O(n ^ 2),因為有 n 個單位根帶入 n-1 項方程式,但是這之後就是 divide and conquer 的重頭戲了


我們根據橡樹的奇偶項分離獨立開來成 2k 與 2k+1 (後面第二項把 Wn ^ (2k + 1) 中的 +1 次方提出來到前面),純粹這樣看並沒有節省任何時間

但是為什麼要這麼作呢?因為這樣可以用到單位根一個有趣的化簡特性

你會發現單位根的平方,值的數量會少一半; 這個特性我們可以從 「單位根事實上就是等分實虛平面上單位圓」 印證,因為正負對稱的關係,平方之後變成相同值,我們可以以數學推得:

會有負號是因為 e ^ (pi * i),也可以理解成旋轉了 180度

所以最後上面看起來鳥鳥的奇偶分類在 k < n/2 就可以變成

你可以看到 Wn ^ 2 已經被取代,並且在 k > n/2 時變成

由於旋轉 180 度的關係,在 k > n/2 時會變成負號

從這邊看到,我們從原本需要計算 n 個點(n-1 次方程式),到現在透過拆一次奇偶變成只需要 n/2 個點; 之後便是不斷遞迴重複拆奇偶

這樣的運算時間複雜度,包含奇偶兩邊要各自遞迴拆,為 O(n log n)

快速傅立葉反轉換(Inverse Discrete Fourier Transform, IDFT)

反轉換,以國高中的角度講就是給點求方程式;

正常來說我們會用矩陣來表示及運算

我們把上面這個係數矩陣叫做 V

為了求 V 的反矩陣,我們神來一筆的把原本的係數次方全部加個負號,這個新的矩陣我們叫它 D(先說這個矩陣後面會證得跟 V 反矩陣很像)

今天我們也是靈機一動的把 D 跟 V 作 dot product 把結果叫做 E

然後來討論 i 與 j對 E 的影響

可以看到,當 i = j 時,事實上就是 n 個 1; 然後 i != j 時,其實就會形成一個等比級數,可以套用等比公式解,但是剛好單位根每 360 度循環,所以相消等於零

於是我們就可以發現,這個 E 事實上就是 N 倍的單位矩陣(只有對角線值為 1, 其他都是零),根據反矩陣的定義就是「與之相乘等於單位矩陣」

我們於是知道 1/n 倍的 D 事實上就是 V 的反矩陣

上圖看起來是不是很熟悉呢,事實上,要作反轉換,我們只需要把係數指數變號,做完另一次 DFT 之後,再除以 n 就好了


先寫到這邊,目前雖然懂了基本觀念,但是中英文兩邊的程式碼觀念一時兜不太起來; 之後還要根據數值分佈狀況分析這樣的算法什麼情況下有好的效能表現,同時因為複數運算會有精確度的疑慮,因此還要針對數值的正確性作檢查

陳奕熹

Written by

陳奕熹

應該要是一個工程師的……

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade