大整数乘法问题.doc

《大整数乘法问题.doc》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、2.4大整数乘法问题算法设计思想：(1)大整数的存储我们知道，在编译系统中，整型数据类型的最大存储空间为8字节，也就是最大能存储232的数据。即使使用双精度浮点数据类型（double），也只能存储最大1.798×10308的数据。如果需要计算10200数量级的整数的乘法，利用的现有的数据类型就无法实现了。所以，为了实现大整数的乘法，需要自己定义一种数据类型，以及对应的基本运算。在该算法中，为了调试和处理方便，我们采用静态整型数组来存放大整数，即用数组的每一个元素存放大整数一位上的数字。然后，分别定义用数组

2、存放的大整数的加法、减法和移位运算。这样，我们就可以用定义的大整数进行后面分治乘法的运算。(2)分治思想将位数是2的次幂的n位的十进制大整数X和Y各分为2段，每段的长为n/2位。则有，X=A×10n/2+B，Y=C×10n/2+D。这样，乘积问题变为这样的分治问题：XY=(A×10n/2+B)(C×10n/2+D)=AC×10n+(AD+CB)×10n/2+BD①如果按①式计算XY，我们可得时间复杂度T(n)=O(n2)（详细论证在课本上）。显然，用①式来计算X和Y的乘积并不比乘法竖式更有效。为了改进算法

3、的计算复杂性，我们把XY写成另一种形式：XY=AC×10n+[(A-B)(D-C)+AC+BD]×10n/2+BD        ②用解递归方程的套用公式法可得②式的时间复杂度T(n)=O(nlog3)=O(n1.59)，该结果有效地减小了算法的时间复杂度。因此，根据②式，我们得到了大整数相乘的分治算法。(3)高位补0的位数处理方法我们提出的分治思想在理论上是可行的，但是在算法具体实现中，程序的递归过程要求每次进行分治计算，即带入②式的大整数X和Y有如下要求：1．X和Y的位数相同。2．X和Y的位数是2的次

4、幂。按照这样的限制，我们只能计算n×n位（n=1,2,4,8,16...）的整数乘法。显然，这样的算法有很大的局限性，它不能处理像132×12758这样更为普遍的问题。因此，我们在算法里采用这样的处理方法：当大整数需要进行分治乘法时，在两个乘数的高位补0，使它们的位数达到相同的2的次幂；分治结束后，将得到的乘积的高位多余的0去除，进行加减等非分治算法运算；以此类推。采用这种高位补0的位数处理方法，实现了任意位大整数的乘法。除了上述三点之外，程序对鲁棒性做了增强，对非法输入和文件错误进行了检测。程序设计代码

5、：/*头文件大数乘法问题.h*/#ifndefKNAP_H#defineKNAP_H#include#include#includeusingnamespacestd;/*定义数制，范围2到10*/#defineSCALE10/*整数的最大位数*/constintMax=1000;/*表示整数的结构体*/structInteger{boolpositive;//整数的正负shortnum[Max];//整数的各位数字，下标从0开始intlength;/

6、/整数的位数};/*两个整数的乘法类*/classMultiply{public:Multiply(char*in,char*out);//构造函数~Multiply();//析构函数voidOutputProduct();//输出大整数的乘积protected:shortCharToInt(charch);//将数字字符转化成整型intAddDigit(Integer&X,Integer&Y);//将位数补充到相同2的次幂位voidInitialInteger(Integer&integer,ifstr

7、eam&in);//文件初始化大整数voidOutputInteger(Integerinteger);//输出大整数integervoidClearZero(Integer&integer);//去除大整数高位多余的0boolPositiveXGreaterThanY(IntegerX,IntegerY);//判断是否非负X大于非负YboolEqualsToZero(Integerinteger);//判断是否等于0IntegerZero();//返回大整数0IntegerGetAbsolute(Int

8、egerinteger);//返回大整数integer的绝对值IntegerGetNegative(Integerinteger);//返回大整数integer的负值IntegerGetLeft(Integerinteger);//取大整数integer左一半IntegerGetRight(Integerinteger);//取大整数integer右一半IntegerLeftShifting(Integerinteger,in