#121 Fourier变换应用小记

大整数问题一直很头疼,采用乘法原理的结果复杂度为\(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)\)的计算复杂度。

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

如果我的文章对你起到了帮助,你可以选择金额不限的捐助,帮助我写出更多的文章。