利用快速傅里葉變換計算多項(xiàng)式乘法

1、Written by szh. 問 題 引 入： 整 數(shù) 加 法 n位數(shù)與n位數(shù)相加 ( (進(jìn)位與當(dāng)前位的加法進(jìn)位與當(dāng)前位的加法 算作算作1 1次運(yùn)算次運(yùn)算) ) n 問 題 引 入： 整 數(shù) 乘 法 1.n位數(shù)與1位數(shù)相乘 n 問 題 引 入： 整 數(shù) 乘 法 2.n位數(shù)與n位數(shù)相乘 (2)中每一位中每一位 同同(1)逐位相乘逐位相乘 (1) (2) 乘法計算次數(shù)乘法計算次數(shù) 2 n 加法計算次數(shù)加法計算次數(shù) 2 2n 總計算次數(shù)總計算次數(shù) 2 3n 時間復(fù)雜度時間復(fù)雜度 2 n 問 題 引 入： 整 數(shù) 乘 法 兩個n位數(shù)相乘的時間復(fù)雜度為 2 n 當(dāng)n非常大時(如n10000時)，利用計

2、算機(jī) 直接計算兩個n位數(shù)的乘積將十分低效。 為了高效進(jìn)行大整數(shù)乘法，需要一種更高 效的算法。 利用快速傅里葉變換計算n位大整數(shù)乘法， 其時間復(fù)雜度為nn 2 log 一、多項(xiàng)式的兩種表達(dá)形式 1、系數(shù)表達(dá) 多項(xiàng)式： 3 3 2 210 xaxaxaaxA n n xa 其系數(shù)為： n aaaa, 210 將系數(shù)寫為向量形式： T n aaaaa),( 210 系數(shù)向量 a稱為多項(xiàng)式 xA的系數(shù)表達(dá)形式。 兩個n次多項(xiàng)式的加法 0 axA(1) n n xbxbxbbxB 2 210 (2) xa 1 2 2 xa n n xa 0 cxC(3)xc1 2 2 xc n n xc 其中， 000

3、 bac， 111 bac,., nnn bac 系數(shù)表達(dá)下兩個n次多項(xiàng)式的加法 的系數(shù)向量 xA T n aaaaa),( 210 的系數(shù)向量 xB T n bbbbb),( 210 的系數(shù)向量 xC T n ccccc),( 210 bac n )()(xBxAxC n+1次加法運(yùn)算次加法運(yùn)算 時間復(fù)雜度： 系數(shù)表達(dá)式下兩個n次多項(xiàng)式的乘法 的系數(shù)向量 xA T n aaaaa),( 210 的系數(shù)向量 xB T n bbbbb),( 210 令 xBxAxC 將a與b中的系數(shù)兩兩相乘。 其時間復(fù)雜度為 2 n 計算計算C(x)C(x)系數(shù)系數(shù) 2、點(diǎn)值表達(dá) n nx axaxaaxA 2

4、 210 對于n次多項(xiàng)式 任取n+1個不同 的點(diǎn) ),( ii yx 根據(jù)n+1個點(diǎn)唯一確定n次多項(xiàng)式系數(shù) 01 ay :未知量 i a i x i y 2 12 xa 11x a n n xa 1 02 ay 2 22 xa 21x a n n xa 2 01 ayn 2 12 n xa 11 n xa n nn xa 1 :已知量 n+1元一次方程組 矩陣形式的方程組 n nnn n n n xxx xxx xxx xxx 2 2 2 22 1 2 11 0 2 00 1 1 1 1 n a a a a 2 1 0 = n y y y y 2 1 0 系數(shù)矩陣行列式不為0 yAa 證明方程

5、具有唯一解 只需證明只需證明 證明系數(shù)矩陣行列式不為0 n nnn n n n xxx xxx xxx xxx 2 2 2 22 1 2 11 0 2 00 1 1 1 1 = nji ji xx 0 由于當(dāng) ji 時，必有 ji xx ，所以 0 矩陣滿秩 因此，方程組 yAa 具有唯一解。 Vandermon de行列式 點(diǎn)值表達(dá) 任取n+1個不同的點(diǎn) ),( ii yx，可確定唯一 n次多項(xiàng)式。 換句話說，對于： ),( ,),(),(),( 221100nn yxyxyxyx 可以作為n次多項(xiàng)式的一種表述形式。 點(diǎn)值表達(dá)： 點(diǎn)值表達(dá)下n次多項(xiàng)式 , 的加法)(xA)(xB ),( ,)

6、,(),(),( 221100nn yxyxyxyx)(xA： ),( ,),(),(),( 221100nn zxzxzxzx)(xB： )()()(xBxAxC 的點(diǎn)值表達(dá)為： ),(),(),( 222111000 zyxzyxzyx)(xC： ),( , nnn zyx 注意A(x),B(x)在相同 的n+1個位置取值 點(diǎn)值表達(dá)為： 時間復(fù)雜度為)(n 需要將A(x),B(x)點(diǎn)值表達(dá)擴(kuò)展到2n+1對 ),( ,),(),(),( 221100nn yxyxyxyx)(xA： ),( ,),(),(),( 221100nn zxzxzxzx)(xB： 點(diǎn)值表達(dá)下n次多項(xiàng)式的乘法 點(diǎn)值表

7、達(dá)為： 可以得到C(x)中n+1對點(diǎn)值： 而C(x)是2n次多項(xiàng)式 表示表示C(x)C(x) ),( ,),(),(),( 22221100nn yxyxyxyx)(xA： ),( ,),(),(),( 22221100nn zxzxzxzx)(xB： 點(diǎn)值表達(dá)下n次多項(xiàng)式的乘法 擴(kuò)展點(diǎn)值表達(dá)為： 可以得到C(x)點(diǎn)值表達(dá)： ),( ,),(),(),( 222222111000nnn zyxzyxzyxzyx 時間復(fù)雜度為)(n 2n+1次乘法運(yùn)算次乘法運(yùn)算 ),( ,),(),(),( 221100nn yxyxyxyx 系數(shù)表達(dá)與點(diǎn)值表達(dá)是等價的 系數(shù)表達(dá)： n n xaxaxaaxA

8、2 210 點(diǎn)值表達(dá)： T n aaaaa),( 210 求值求值插值插值 拉格朗日 插值公式 系數(shù)表達(dá)與點(diǎn)值表達(dá)比較及轉(zhuǎn)換 系 數(shù) 表 達(dá) 點(diǎn) 值 表 達(dá) n aaa, 10 求值求值插值插值 n bbb, 10 普通乘法 時間 )( 2 n n ccc 210 , )(),( 0 12 0 12nn BA )(),( 1 12 1 12nn BA )(),( 2 12 2 12 n n n n BA 點(diǎn)值乘法 時間)(n )( 0 12 n C )( 1 12 n C )( 2 12 n n C 時間 )log( 2 nn 時間 )log( 2 nn 一種快速計算多項(xiàng)式乘法的算法(系數(shù)表示

9、) 1、對A,B進(jìn)行求值，時間復(fù)雜度 算法描述：算法描述： 在上述假設(shè)下，求值與插值時在上述假設(shè)下，求值與插值時 間復(fù)雜度均為間復(fù)雜度均為 )log( 2 nn )log( 2 nn 2、對A,B進(jìn)行點(diǎn)值乘法，時間復(fù)雜度)(n 3、對結(jié)果進(jìn)行插值，時間復(fù)雜度)log( 2 nn 二、快速求值 n aaa, 10 求值求值 n bbb, 10 )(),( 0 12 0 12nn BA )(),( 1 12 1 12nn BA )(),( 2 12 2 12 n n n n BA 時間 )log( 2 nn 若任取2n+1個點(diǎn)直接求值， n iniii xbxbxbbxB 2 210 計算 k i

10、 x所需時間: )(n 計算加法所需時間:)(n 在每一個點(diǎn)處求值時間 )(n 對所有點(diǎn)求值時間:)( 2 n 需要降為:)log( 2 nn 二、快速求值 n aaa, 10 求值求值 n bbb, 10 )(),( 0 12 0 12nn BA )(),( 1 12 1 12nn BA )(),( 2 12 2 12 n n n n BA 時間 )log( 2 nn 適當(dāng)選取2n+1個點(diǎn)與算法， 每個點(diǎn)求值時間可以降為: )(log 2 n 對所有點(diǎn)求值時間將為: )log( 2 nn 特殊取值： 2n+1次單位復(fù)數(shù)根 單位復(fù)數(shù)根 定義：定義： n次單位復(fù)數(shù)根是滿足1 n 的復(fù)數(shù). n次單

11、位復(fù)數(shù)根恰好有n個 求解求解 由歐拉公式知, )2sin()2cos(1 2 kike ik nik e 2 i n k e 2 單位復(fù)數(shù)根 主主n次單位根：次單位根： n次單位復(fù)數(shù)根幾何意義次單位復(fù)數(shù)根幾何意義 k=1 i n k e 2 i n n e 2 ) 2 sin() 2 cos( n ki n k 左圖為8次單位根 在復(fù)平面上的分布。 n次單位根 在復(fù)平面上均勻分布 n 0(8) 13 4 5 7 2 6 單位復(fù)數(shù)根的性質(zhì) n個n次單位復(fù)數(shù)根 1210 , n nnnn 乘法意義下構(gòu)成群：乘法意義下構(gòu)成群： 在乘法意義下構(gòu)成群。 該群與群 nn Z ,(整數(shù)模n)同構(gòu)，即 nji

12、 n ji n j n i n mod)( 1 0 n nn 單位復(fù)數(shù)根的性質(zhì) 消去引理：消去引理： k n n k i dk dn ee dn dk i 2 2 0, 0, 0kdn 對于偶數(shù)對于偶數(shù)n0： 1 2 2 n n 單位復(fù)數(shù)根的性質(zhì) 折半引理：折半引理： ,0|)( 2 Nini i n , 2 0|)( 2 2/ Ni n i i n n個n次單位復(fù)數(shù)根的平方的集合，就是n/2個 n/2次單位復(fù)數(shù)根的集合。 單位復(fù)數(shù)根的性質(zhì) 折半引理的幾何意義：折半引理的幾何意義： 8次單位復(fù)數(shù)根 在復(fù)平面上的分布 0(8) 1 2 3 4 5 6 7 1 4 2 8 21 8 )( 2 8

13、10 8 25 8 )( 1 4 21 8 25 8 )()( 單位復(fù)數(shù)根的性質(zhì) 2/ 2/ 2 k n k n 折半引理的證明：折半引理的證明： 由消去引理知： 此時又有 1 2/ n n k n nk n 2/222/ )()( k n nk n 單位復(fù)數(shù)根的性質(zhì) 求和引理：求和引理： 1 0 0 n i n k n k是非負(fù)整數(shù)， k不是n的倍數(shù) 求和引理證明：求和引理證明： 1 0 n i n k n = 1 1)( k n nk n 1 1)( k n kn n = 1 1)1 ( k n k = 0 k不是n的倍數(shù)，1 k n 離散傅里葉變換(DFT) 回顧 我們希望計算 n i

14、i ix axA 0 )( 1210 , n nnnn 在 處的值 （即在n+1個n+1次單位根處） 假設(shè)A以系數(shù)形式給出，系數(shù)向量 T n aaaa),( 10 離散傅里葉變換(DFT) n j kj nj k nk aAy 0 )( 定義結(jié)果： nk, 1 ,0 T n yyyy),( 10 就是系數(shù)向量 T n aaaa),( 10 的離散傅里葉變換 采用普通乘法進(jìn)行計算，時 間復(fù)雜度為)( 2 n 離散傅里葉變換與快速傅里葉變換(FFT) 有必要利用單位復(fù)數(shù)根的特 殊性質(zhì)，降低時間復(fù)雜度 計算離散傅里葉變換 離散傅里葉變換與快速傅里葉變換(FFT) n n xaxaxaaxA 2 21

15、0 對于n次多項(xiàng)式： 12 3 12 2 02 1 02 0 )()()()(xxaxaxxaxa 2/)1(222 5 22 4 )()()( n n xxaxxaxa 此處假設(shè)n+1是2的整數(shù)次冪 2 1 - 1 2 420 0 )( n n xaxaxaaxA 偶數(shù)下標(biāo) 2 1- 2 531 1 )( n n xaxaxaaxA 奇數(shù)下標(biāo) )()()( 2120 xxAxAxA 離散傅里葉變換與快速傅里葉變換(FFT) )()()( 2120 xxAxAxA 對于 求A(x)在 0 1n 1 1n ,., n n 1 處取值轉(zhuǎn)化為： 求(n-1)/2次多項(xiàng)式 )( 0 xA, )( 1

16、xA在 20 1) ( n , 21 1) ( n , 2 1) ( n n 處取值 處取值即 0 2/ )1( n , 0 2/ )1( n ,., 0 2/ )1( n 折半引理折半引理 然后將結(jié)果相加 得到A(x) 離散傅里葉變換與快速傅里葉變換(FFT) 遞歸地處理 )( 0 xA )( 1 xA 分解成兩個相似 的子問題，規(guī)模 減半 拆分時,需要把 n+1個系數(shù)拆成兩 部分.時間復(fù)雜度 )(n 離散傅里葉變換與快速傅里葉變換(FFT) 時間復(fù)雜度遞推公式 )() 2 (2)(n n TnT 規(guī)模為n的時間復(fù)雜度 拆分成2個n/2規(guī)模的子問題 拆分問題代價 求解該遞推式，有 )log(

17、)( 2 nnnT 采用FFT,可以在)log( 2 nn時間內(nèi)實(shí)現(xiàn)插值 插值插值 n ccc 210 , )( 0 12 n C )( 1 12 n C )( 2 12 n n C 時間 )log( 2 nn 利用快速傅里葉變換實(shí)現(xiàn)插值回顧 不妨先考慮n次多 項(xiàng)式A(x)的插值 依然假設(shè)n+1是2 的整數(shù)次冪 利用快速傅里葉變換實(shí)現(xiàn)插值 n j kj nj k nk aAy 0 )( 離散傅里葉變換中的一項(xiàng)： 將離散傅里葉變換寫成矩陣形式：aVy n 1 n y y y y 2 1 0 = 2 1 2 11 2 1 4 1 2 1 1 2 11 1 1 1 1111 n n n n n n

18、n nnn n nnn n a a a a 2 1 0 易知： 0| 1 n V 1n V可逆 利用快速傅里葉變換實(shí)現(xiàn)插值 下面證明： 1 1 n V),(ji處元素 1 1 n v ij n ij 考慮： 1 1 1 nn VV),(ji處元素ij p n k ijk n n k kj n ik n ij nn p 0 1 0 1 1 11 當(dāng)ij 時： 1 ij p 當(dāng)ij 時： 0 ij p 求和引理 nnn IVV 1 1 1 利用快速傅里葉變換實(shí)現(xiàn)插值 T n aaaa),( 10 可以求出 n k ki nki y n a 0 1 1 1 而在離散傅里葉變換中： n j kj njk ay 0 互換 ya, 1 替換 與離散傅里葉 變換相似 )log( 2 nn得到了的插值算法 利用快速傅里葉變換計算多項(xiàng)式乘法 系 數(shù) 表 達(dá) 點(diǎn) 值 表 達(dá) n aaa, 10 求值求值插值插值 n bbb, 10 普通乘法 時間 )( 2 n n ccc 210 , )(),( 0 12 0 12nn BA )(),( 1 12 1 12nn BA )(),( 2 12 2 12 n n n n BA