大整数问题一直很头疼，采用乘法原理的结果复杂度为$O(n^{2})$，最近看傅里叶变换有尝试用傅里叶变换加以改进。

设

$$ a=(a_{N-1}a_{N-2}…a_{1}a_{0}){10}=a{N-1}10^{N-1}+…+a_{0}10^{0}] [b=(b_{N-1}b_{N-2}…b_{1}b_{0}){10}=b{N-1}10^{N-1}+…+b_{0}10^{0} $$

两个式子的乘积

$$ c = ab = c_{2N-2}10^{2N-2}+c_{2N-3}10^{2N-3}+…+c_{1}10^{1}+c_{0}10^{0} $$

其中

$$ c_{k}=\sum_{i+j=k}a_{i}b_{j},(i=0,…,N-1) $$

这种算法的时间复杂度为$O(n^{2})$。

逆天的是，${c_{k}}$居然逆天的等于${a_{k}}$和${b_{k}}$点的卷积。我们知道，卷积可以通过傅里叶变换的方式转化为普通乘法（函数卷积的傅里叶变换是函数傅里叶变换的乘积）。 于是，我们有： （1）求${a_{i}}$和${b_{j}}$的傅里叶变换（离散）${A_{i}}$和${B_{j}}$ （2）${A_{i}}$和${B_{j}}$逐项相乘得到${C_{k}}$ （3）对${C_{k}}$求傅里叶逆变换，得到${c_{k}}$ （4）进位，出结果

对复向量${x_{N-1},…,x_{1},x_{0}}$，离散傅里叶变换为：

$$ X_{k}=\sum_{n=0}^{N-1}x_{n}e^{\frac{-2i\pi nk}{N}},(k=0,…,N-1) $$

逆变换公式为：

$$ x_{k}=\frac{1}{N}\sum_{k=0}^{N-1}X_{k}e^{\frac{-2i\pi kn}{N}},(n=0,…,N-1) $$

例： 三位数（$N=3$）$a=456,b=987$，求c=ab。 结果为：c=450072。共 6 位数字，$N$扩展到$2^3 = 8$。

$$ { a_7, a_6, a_5, a_4, a_3, a_2, a_1, a_0 } = { 0, 0, 0, 0, 0, 4, 5, 6 } $$

$$ { b_7, b_6, b_5, b_4, b_3, b_2, b_1, b_0 } = { 0, 0, 0, 0, 0, 9, 8, 7 } $$

令：

$$ \omega=e^{\frac{-2i\pi}{N}}=e^{\frac{-2i\pi}{8}}=e^{\frac{-i\pi}{4}}=cos\left(-\frac{\pi}{4}\right)+isin\left(-\frac{\pi}{4}\right)=\frac{\sqrt{2}}{2}-i\frac{\sqrt{2}}{2} \approx 0.7-0.7i $$

为了方便：

$$ \begin{eqnarray} && \omega^{8} =\omega^{0} = 1 \nonumber\ && \omega^{9} =\omega^{1} \approx 0.7-0.7i \nonumber\ && \omega^{10}=\omega^{2} = -i \nonumber\ && \omega^{11}=\omega^{3} \approx -0.7-0.7i \nonumber\ && \omega^{12}=\omega^{4} = -1 \nonumber\ && \omega^{13}=\omega^{5} \approx -0.7+0.7i \nonumber\ && \omega^{14}=\omega^{6} = i \nonumber\ && \omega^{15}=\omega^{7} \approx 0.7+0.7i \nonumber \end{eqnarray} $$

注意到当$n>2$时，$a_{n}=0$，于是

$$ \begin{eqnarray} && A_0 = a_0\times \omega^{0\times 0} + a_1\times \omega^{1\times 0} + a_2\times \omega^{2\times 0} = 6\times\omega^{0} + 5\times\omega^{0} + 4\times\omega^{0} = 15 \nonumber\ \end{eqnarray} $$

$$ \begin{eqnarray} && A_1 = a_0\times \omega^{0\times 1} + a_1\times \omega^{1\times 1} + a_2\times \omega^{2\times 1} = 6\times\omega^{0} + 5\times\omega^{1} + 4\times\omega^{2} = \nonumber\ \end{eqnarray} $$

$$ \begin{eqnarray} && A_2 = a_0\times \omega^{0\times 0} + a_1\times \omega^{1\times 2} + a_2\times \omega^{2\times 2} = 6\times\omega^{0} + 5\times\omega^{2} + 4\times\omega^{4} = \nonumber\ \end{eqnarray} $$

$$ \begin{eqnarray} && A_3 = a_0\times \omega^{0\times 0} + a_1\times \omega^{1\times 3} + a_2\times \omega^{2\times 3} = 6\times\omega^{0} + 5\times\omega^{3} + 4\times\omega^{6} = \nonumber\ \end{eqnarray} $$

$$ \begin{eqnarray} && A_4 = a_0\times \omega^{0\times 0} + a_1\times \omega^{1\times 4} + a_2\times \omega^{2\times 4} = 6\times\omega^{0} + 5\times\omega^{4} + 4\times\omega^{8} = \nonumber\ \end{eqnarray} $$

$$ \begin{eqnarray} && A_5 = a_0\times \omega^{0\times 0} + a_1\times \omega^{1\times 5} + a_2\times \omega^{2\times 5} = 6\times\omega^{0} + 5\times\omega^{5} + 4\times\omega^{10} = \nonumber\ \end{eqnarray} $$

$$ \begin{eqnarray} && A_6 = a_0\times \omega^{0\times 0} + a_1\times \omega^{1\times 6} + a_2\times \omega^{2\times 6} = 6\times\omega^{0} + 5\times\omega^{6} + 4\times\omega^{12} = \nonumber\ \end{eqnarray} $$

$$ \begin{eqnarray} && A_7 = a_0\times \omega^{0\times 0} + a_1\times \omega^{1\times 7} + a_2\times \omega^{2\times 7} = 6\times\omega^{0} + 5\times\omega^{7} + 4\times\omega^{14} = \nonumber \end{eqnarray} $$

同样，当$n>2$时，$b_{n}=0$，于是

$$ \begin{eqnarray} && B_0 = b_0\times \omega^{0\times 0} + b_1\times \omega^{1\times 0} + b_2\times \omega^{2\times 0} = 7\times\omega^{0} + 8\times\omega^{0} + 9\times\omega^{0} = 24 \nonumber\ \end{eqnarray} $$

$$ \begin{eqnarray} && B_1 = b_0\times \omega^{0\times 1} + b_1\times \omega^{1\times 1} + b_2\times \omega^{2\times 1} = 7\times\omega^{0} + 8\times\omega^{1} + 9\times\omega^{2} = \nonumber\ \end{eqnarray} $$

$$ \begin{eqnarray} && B_2 = b_0\times \omega^{0\times 2} + b_1\times \omega^{1\times 2} + b_2\times \omega^{2\times 2} = 7\times\omega^{0} + 8\times\omega^{2} + 9\times\omega^{4} = \nonumber\ \end{eqnarray} $$

$$ \begin{eqnarray} && B_3 = b_0\times \omega^{0\times 3} + b_1\times \omega^{1\times 3} + b_2\times \omega^{2\times 3} = 7\times\omega^{0} + 8\times\omega^{3} + 9\times\omega^{6} = \nonumber\ \end{eqnarray} $$

$$ \begin{eqnarray} && B_4 = b_0\times \omega^{0\times 4} + b_1\times \omega^{1\times 4} + b_2\times \omega^{2\times 4} = 7\times\omega^{0} + 8\times\omega^{4} + 9\times\omega^{8} = \nonumber\ \end{eqnarray} $$

$$ \begin{eqnarray} && B_5 = b_0\times \omega^{0\times 5} + b_1\times \omega^{1\times 5} + b_2\times \omega^{2\times 5} = 7\times\omega^{0} + 8\times\omega^{5} + 9\times\omega^{10} = \nonumber\ \end{eqnarray} $$

$$ \begin{eqnarray} && B_6 = b_0\times \omega^{0\times 6} + b_1\times \omega^{1\times 6} + b_2\times \omega^{2\times 6} = 7\times\omega^{0} + 8\times\omega^{6} + 9\times\omega^{12} = \nonumber\ \end{eqnarray} $$

$$ \begin{eqnarray} B_7 = b_0\times \omega^{0\times 7} + b_1\times \omega^{1\times 7} + b_2\times \omega^{2\times 7} = 7\times\omega^{0} + 8\times\omega^{7} + 9\times\omega^{14} = \nonumber \end{eqnarray} $$

于是得到${A_i}$和${B_i}$

$$ \begin{eqnarray} && {A_7,A_6,A_5,A_4,A_3,A_2,A_1,A_0}={,,,,,,,15} \nonumber\ \end{eqnarray} $$

$$ \begin{eqnarray} && {B_7,B_6,B_5,B_4,B_3,B_2,B_1,B_0}={,,,,,,,24} \nonumber \end{eqnarray} $$

再求${A_i}$和${B_i}$的点积得到${C_{k}}$：

$$ \begin{eqnarray} && {C_7,C_6,C_5,C_4,C_3,C_2,C_1,C_0}={,,,,,,,360} \nonumber \end{eqnarray} $$

求${C_{k}}$的离散傅里叶逆变换，令

$$ \omega=e^{\frac{2i\pi}{N}}=e^{\frac{2i\pi}{8}}=e^{\frac{i\pi}{4}}=cos\left(\frac{\pi}{4}\right)+isin\left(\frac{\pi}{4}\right)=\frac{\sqrt{2}}{2}+i\frac{\sqrt{2}}{2} \approx 0.7+0.7i $$

为了方便：

$$ \begin{eqnarray} && \omega^{8} =\omega^{0} = 1 \nonumber\ \end{eqnarray} $$

$$ \begin{eqnarray} && \omega^{9} =\omega^{1} \approx 0.7+0.7i \nonumber\ \end{eqnarray} $$

$$ \begin{eqnarray} && \omega^{10}=\omega^{2} = -i \nonumber\ \end{eqnarray} $$

$$ \begin{eqnarray} && \omega^{11}=\omega^{3} \approx -0.7-0.7i \nonumber\ \end{eqnarray} $$

$$ \begin{eqnarray} && \omega^{12}=\omega^{4} = -1 \nonumber\ \end{eqnarray} $$

$$ \begin{eqnarray} && \omega^{13}=\omega^{5} \approx -0.7+0.7i \nonumber\ \end{eqnarray} $$

$$ \begin{eqnarray} && \omega^{14}=\omega^{6} = i \nonumber\ \end{eqnarray} $$

$$ \begin{eqnarray} && \omega^{15}=\omega^{7} \approx 0.7+0.7i \nonumber \end{eqnarray} $$

于是计算$c_{i}$得到：

于是获得${c_{i}}$，，于是${c_i}$就是大整数的计算结果。 但是可惜离散傅里叶变换的时间复杂度还是$O(n^{2})$。关键在于：直接进行离散傅里叶变换的计算复杂度是$O(N^2)$。快速傅里叶变换可以计算出与直接计算相同的结果，但只需要$O(NlogN)$的计算复杂度。

部分运算结果没有写完，时间问题，改日再补。