大整数问题一直很头疼，采用乘法原理的结果复杂度为$O(n^{2})$，最近看傅里叶变换有尝试用傅里叶变换加以改进。
设
两个式子的乘积
$$ 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)$的计算复杂度。
部分运算结果没有写完，时间问题，改日再补。