以下为《分治法求解大整数相乘问题解题报告模板》的无排版文字预览，完整格式请下载

下载前请仔细阅读文字预览以及下方图片预览。图片预览是什么样的，下载的文档就是什么样的。

大整数相乘

问题描述：

用分治法设计一个两个n位大整数的乘法运算算法。假定乘法运算的基本操作为bit位运算（包括比特加、移位等），要求分治法的时间复杂度小于O(n2)。

算法设计：

同问题描述。

算法提示：

将n位的二进制整数X和Y各分为2段，每段的长为n/2位(为简单起见，假设n是2的幂)，如图所示。

由此，X=A2n/2+B ，Y=C2n/2+D。这样，X和Y的乘积为：

XY=(A2n/2+B)(C2n/2+D)=AC2n+(AD+CB)2n/2+BD (1)

如果按式(1)计算XY，必须进行4次n/2位整数的乘法(AC，AD，BC和BD)，以及3次不超过n位的整数加法(分别对应某某(1)中的加号)，此外还要做2次移位(分别对应某某(1)中乘2n和乘2n/2)。所有这些加法和移位共用O(n)步运算。设T(n)是2个n位整数相乘所需的运算总数，则由式(1)，有：

(2)

由此可得T(n)=O(n2)。要想改进算法的计算复杂性，必须减少乘法次数。把XY写成另一种形式:

XY=AC2n+[(A-B)(D-C)+AC+BD]2n/2+BD (3)

虽然，式(3)仅需做3次n/2位整数的乘法(AC，BD和(A-B)(D-C))，6次加、减法和2次移位。由此可得:

(4)

可得其解为T(n)=O(nlog3)=O(n1.59)。

数据输入：

由文件input.txt提供输入数据。文件第1、2行分别是n位大整数X和Y（用二进制表示），用空格分隔，第3行是n（假设n是2的幂，n

以上为《分治法求解大整数相乘问题解题报告模板》的无排版文字预览，完整格式请下载

下载前请仔细阅读上面文字预览以及下方图片预览。图片预览是什么样的，下载的文档就是什么样的。