大整数的乘法

2019-01-23 本文已影响0人 ZakWind

将n位二进制整数X和Y都分为2段，每段的长为n/2位（为叙述简单，假设n是2的幂）

由此， $\begin{eqnarray*}X&=&A\times2^{n/2}+B\\Y&=&C\times2^{n/2}+D\end{eqnarray*}$

这样，X和Y的乘积为 $\begin{eqnarray*}XY&=&(A2^{n/2}+B)(C2^{n/2}+D)\\&=&AC2^n+(AD+BC)2^{n/2}+BD\end{eqnarray*}$

为减少乘法的次数，将上式转换为 $XY=AC2^n+((A-B)(D-C)+AC+BD)2^{n/2}+BD$
时间复杂度 $T(n)=O(n^{1.59})$