本章涉及知識(shí)點(diǎn)：

1蜕提、多項(xiàng)式乘法的時(shí)間復(fù)雜度

2乌妙、多項(xiàng)式的表示：系數(shù)

3使兔、多項(xiàng)式的表示：點(diǎn)值

4、復(fù)數(shù)的表示

5藤韵、單位復(fù)數(shù)根

6虐沥、單位復(fù)數(shù)根的性質(zhì)—消去引理

7、單位復(fù)數(shù)根的性質(zhì)—折半引理

8泽艘、離散傅里葉變換：DFT和IDFT

9欲险、快速傅里葉變換：FFT

10、FFT求解多項(xiàng)式乘法的步驟

11匹涮、python編程實(shí)戰(zhàn)FFT大數(shù)乘法

12天试、結(jié)果分析

一、多項(xiàng)式乘法的時(shí)間復(fù)雜度

數(shù)學(xué)中然低，我們可以將任意一個(gè)n位的數(shù)字寫為一個(gè)n-1次多項(xiàng)式喜每，如456可以寫為

數(shù)字轉(zhuǎn)為多項(xiàng)式

即可抽象定義出以x為變量的多項(xiàng)式函數(shù)A(x)

多項(xiàng)式函數(shù)

其中aj表示：長(zhǎng)度為N-1位數(shù)字的第j為數(shù)字

例如要計(jì)算456 * 123 = ？雳攘，則我們用多項(xiàng)式A(x)和B(x)來分別表示其各自的數(shù)字带兜，C(x)表示兩個(gè)多項(xiàng)式的乘積

兩個(gè)數(shù)字的多項(xiàng)式

由乘法的運(yùn)算規(guī)則，兩個(gè)數(shù)的每一位數(shù)字都要與另一個(gè)數(shù)的每一位相乘吨灭，最后相加同一位上所有的數(shù)字鞋真，得到乘積中該位的數(shù)字，即

多項(xiàng)式乘法

將x=10為基帶入結(jié)果沃于，即可以得到456 * 123 =?4 * 10**4 + 13 * 10**3 + 28 * 10**2 + 27 * 10 + 18 =?56088

我們可以歸納出乘積C(x)的每一位數(shù)字的計(jì)算關(guān)系為

乘積數(shù)位的計(jì)算

其中cj表示：乘積數(shù)中的第j位的數(shù)字

則乘積多項(xiàng)式C(x)可以寫為

乘積多項(xiàng)式

至此我們可以看到涩咖，由于受限于乘法運(yùn)算自身的規(guī)則，計(jì)算兩個(gè)多項(xiàng)式乘積（將數(shù)字轉(zhuǎn)換為多項(xiàng)式）的時(shí)間復(fù)雜度為：繁莹，當(dāng)n很大的時(shí)候復(fù)雜度將非常高

那么需要研究的問題就是：有沒有方法可以高效的提高多項(xiàng)式乘法復(fù)雜度呢檩互？

二、多項(xiàng)式的表示：系數(shù)

為了降低多項(xiàng)式乘法的復(fù)雜度咨演，我們首先需要了解幾個(gè)數(shù)學(xué)知識(shí)

從多項(xiàng)式函數(shù)的定義闸昨，我們將所有系數(shù)視為系數(shù)向量，而由全部系數(shù)組成的向量a叫做該多項(xiàng)式的系數(shù)表達(dá)

系數(shù)表達(dá)

PS：乘積多項(xiàng)式C(x)的系數(shù)向量cj薄风，也稱輸入向量a和b的卷積饵较，記為

卷積運(yùn)算

從之前的分析可知，要計(jì)算出乘積C(x)的每一個(gè)系數(shù)向量cj遭赂，需要的時(shí)間復(fù)雜度為

三循诉、多項(xiàng)式的表示：點(diǎn)值

我們?nèi)我膺x取n個(gè)不同的自變量x帶入多項(xiàng)式函數(shù)A(x)進(jìn)行求值運(yùn)算，將得到n個(gè)不同數(shù)值的y撇他，即

求值運(yùn)算

則多項(xiàng)式的點(diǎn)值表達(dá)就是由這n個(gè)數(shù)值點(diǎn)組成的集合

點(diǎn)值表達(dá)

因?yàn)榭梢赃x取任意n個(gè)不同點(diǎn)所構(gòu)成的集合茄猫，所有一個(gè)多項(xiàng)式可以有很多不同的點(diǎn)值表達(dá)

我們把任意n個(gè)點(diǎn)構(gòu)成的集合叫做點(diǎn)值表達(dá)的基

從點(diǎn)值表達(dá)的基入手，選取適當(dāng)?shù)膞k來優(yōu)化多項(xiàng)式乘法效率困肩，為此划纽，我們選取單位復(fù)數(shù)根作為多項(xiàng)式的基

四、復(fù)數(shù)的表示

復(fù)數(shù)的定義：設(shè)a锌畸，b為實(shí)數(shù)勇劣，則形如的數(shù)稱為復(fù)數(shù)，其中a稱為實(shí)部潭枣，b稱為虛部

PS：當(dāng)a=0時(shí)比默，復(fù)數(shù)為純虛數(shù)；當(dāng)b=0時(shí)卸耘，復(fù)數(shù)可視為實(shí)數(shù)

將復(fù)數(shù)的實(shí)部與虛部的平方和的正平方根值稱為該復(fù)數(shù)的模退敦，即

復(fù)數(shù)的模

五、單位復(fù)數(shù)根

任意一個(gè)復(fù)數(shù)w蚣抗，其n次冪的結(jié)果為1侈百，就稱復(fù)數(shù)w是n次單位復(fù)數(shù)根，即

n次單位復(fù)數(shù)根

可以看到翰铡，n次單位復(fù)數(shù)根有n個(gè)钝域，其幾何意義為：n個(gè)單位復(fù)數(shù)根均勻的分布在以復(fù)平面原點(diǎn)為圓心的單位圓上

n次單位復(fù)數(shù)根的幾何意義

在幾何意義的單位圓中，我們將圓周角均分成n份锭魔，則叫做單位根的幅角

由歐拉公式得

歐拉公式

我們定義表示一個(gè)n次單位根例证，則

主n次單位根

又被稱為主n次單位根，而其余迷捧、等叫做n次單位根的冪次织咧，記為：胀葱，則

n次單位根的冪次

可以很容易知道

n次單位根的性質(zhì)

下面我們證明n次單位根的兩個(gè)性質(zhì)

六、單位復(fù)數(shù)根的性質(zhì)—消去引理

設(shè)d>0為任何一個(gè)整數(shù)笙蒙，則

消去引理

七抵屿、單位復(fù)數(shù)根的性質(zhì)—折半引理

由

折半引理

則可以得到

折半引理

至此，可以看到通過消去和折半引理捅位，我們將n的規(guī)模降低到了原來的一半

八轧葛、離散傅里葉變換：DFT和IDFT

回顧之前我們的多項(xiàng)式函數(shù)

多項(xiàng)式函數(shù)

我們將n次單位根的冪次項(xiàng)：依次帶入A(x)焰雕，則得到

離散傅里葉正變換

記向量是系數(shù)向量的離散傅里葉變換衷笋，也稱離散傅里葉正變換（DFT）

則對(duì)應(yīng)的離散傅里葉逆變換（IDFT）為

離散傅里葉逆變換

可以看到：

（1）DFT對(duì)應(yīng)著多項(xiàng)式求值

（2）IDFT對(duì)應(yīng)著插值，即求多項(xiàng)式的系數(shù)

九淀散、快速傅里葉變換：FFT

由DFT定義可知右莱，將全部依次帶入A(x)計(jì)算出多項(xiàng)式的時(shí)間復(fù)雜度仍然是

此時(shí)我們就需要利用之前所講的n次單位復(fù)數(shù)根的知識(shí)郭膛，將A(x)中的偶數(shù)下標(biāo)和奇數(shù)下標(biāo)的系數(shù)晨抡，分別用兩個(gè)新的多項(xiàng)式A1(x)和A2(x)來表示，即

偶數(shù)下標(biāo)的多項(xiàng)式

奇數(shù)下標(biāo)的多項(xiàng)式

注意：A(x)的次數(shù)界為n则剃，A1(x)的次數(shù)界為n/2耘柱，A2(x)的次數(shù)界也為n/2

則可以得到A(x)和A1(x)、A2(x)的關(guān)系為

多項(xiàng)式函數(shù)關(guān)系

我們將帶入得棍现，其中

快速傅里葉變換1

至此调煎，我們就得到了在之間的所有求值

下面還需要計(jì)算之間的的值，根據(jù)折半引理己肮，我們將帶入得

快速傅里葉變換2

至此士袄，我們就得到了之間的所有求值

觀察上面兩個(gè)式子，不難發(fā)現(xiàn)：

（1）和的計(jì)算式子里只有一個(gè)常數(shù)項(xiàng)互為相反數(shù)

（2）在之間枚舉出后谎僻，就可以在的時(shí)間里得到的

（3）原問題的規(guī)穆α縮小了一半（分治法的思想）

至此，我們利用數(shù)學(xué)中n次單位復(fù)數(shù)根的性質(zhì)艘绍，將DFT優(yōu)化為FFT（快速傅里葉正變換）赤拒，即

快速傅里葉正變換

十、FFT求解多項(xiàng)式乘法的步驟

通過以上的研究，我們可以總結(jié)出使用FFT計(jì)算多項(xiàng)式乘法的時(shí)間復(fù)雜度

FFT計(jì)算多項(xiàng)式乘法的時(shí)間復(fù)雜度

FFT利用n次單位復(fù)數(shù)根和分治法的思想挎挖，將多項(xiàng)式乘法的時(shí)間復(fù)雜度由降低到了

最后我們可以總結(jié)出求解多項(xiàng)式乘法的高效算法步驟為：

（1）加倍次數(shù)界：由分治法的思想这敬，將兩個(gè)多項(xiàng)式的次數(shù)界補(bǔ)全為2的冪次

（2）求值：通過FFT計(jì)算出兩個(gè)多項(xiàng)式的點(diǎn)值表達(dá)，即2n次單位復(fù)數(shù)根的多項(xiàng)式函數(shù)取值

（3）逐點(diǎn)相乘：將兩個(gè)多項(xiàng)式的點(diǎn)值依次相乘肋乍，得到相乘結(jié)果的點(diǎn)值

（4）插值：通過IDFT計(jì)算相乘結(jié)果的點(diǎn)值鹅颊，得到相乘結(jié)果的每一個(gè)系數(shù)

十一、python編程實(shí)戰(zhàn)FFT大數(shù)乘法

計(jì)算離散傅里葉正變換

計(jì)算離散傅里葉逆變換

FFT

IFFT

使用矩陣乘法的DFT和FFT

十二墓造、結(jié)果分析

我們隨便用兩個(gè)386位和422位的整數(shù)，進(jìn)行下面實(shí)驗(yàn)比較計(jì)算乘法的時(shí)間消耗

（1）不使用矩陣乘法的離散傅里葉變換DFT

（2）使用矩陣乘法的離散傅里葉變換DFT

（3）使用矩陣乘法的快速傅里葉變換FFT

（4）直接使用numpy封裝的FFT

運(yùn)行代碼锚烦，實(shí)驗(yàn)結(jié)果如下

結(jié)果分析

至此觅闽，我們可以總結(jié)出

（1）FFT采用分治算法的思想，利用數(shù)學(xué)中n次單位復(fù)數(shù)根的性質(zhì)涮俄，將時(shí)域轉(zhuǎn)化為頻域蛉拙，再到頻域轉(zhuǎn)化為時(shí)域，非常高效的提高了多項(xiàng)式乘法效率彻亲！

（2）我們根據(jù)數(shù)學(xué)理論一步步封裝的FFT和numpy封裝的FFT性能上非常接近

案例代碼見：大數(shù)乘法—多項(xiàng)式與快速傅里葉變換