大整数乘法

                                                                                     大整数乘法                                                                                                                                                          

分析算法计算复杂性时，加法乘法当做基本运算来处理，即一次加法或者乘法当做一个仅取决于计算机硬件处理速度的常数。

正常的二进制整数X,Y要用O(n2)才能算出。如果分割为两段，

X=A2^(n/2)+B,Y=C2^(n/2)+D。

XY = (A2^(n/2)+B)(C2^(n/2)+D)=AC2^n+(AD+BC)2^(n/2)+BD

要进行4次N/2位整数的乘法，以及3次不超过2n为的整数加法，好要做2次移位。

T(n) = O(n^2);

XY=AC2^n+((A-B)(D-C)+AC+BD)2^(n/2)+BD

仅作3次N/2位整数的乘法，6次加减法，2次移位..

时间复杂度变为t(n)=O(n^1.59)

本文转自博客园xingoo的博客，原文链接：大整数乘法，如需转载请自行联系原博主。