大整数乘法问题.doc

2.4 大整数乘法问题算法设计思想：(1) 大整数的存储我们知道，在编译系统中，整型数据类型的最大存储空间为8字节，也就是最大能存储232的数据。即使使用双精度浮点数据类型（double），也只能存储最大1.79810308的数据。如果需要计算10200数量级的整数的乘法，利用的现有的数据类型就无法实现了。所以，为了实现大整数的乘法，需要自己定义一种数据类型，以及对应的基本运算。在该算法中，为了调试和处理方便，我们采用静态整型数组来存放大整数，即用数组的每一个元素存放大整数一位上的数字。然后，分别定义用数组存放的大整数的加法、减法和移位运算。这样，我们就可以用定义的大整数进行后面分治乘法的运算。(2) 分治思想将位数是2的次幂的n位的十进制大整数X和Y各分为2段，每段的长为n/2位。则有，X=A10n/2+B ，Y=C10n/2+D。这样，乘积问题变为这样的分治问题：XY=(A10n/2+B)(C10n/2+D)=AC10n+(AD+CB)10n/2+BD 如果按式计算XY，我们可得时间复杂度T(n)=O(n2)（详细论证在课本上）。显然，用式来计算X和Y的乘积并不比乘法竖式更有效。为了改进算法的计算复杂性，我们把XY写成另一种形式：XY=AC10n+(A-B)(D-C)+AC+BD10n/2+BD 用解递归方程的套用公式法可得式的时间复杂度T(n)=O(nlog3)=O(n1.59)，该结果有效地减小了算法的时间复杂度。因此，根据式，我们得到了大整数相乘的分治算法。(3) 高位补0的位数处理方法我们提出的分治思想在理论上是可行的，但是在算法具体实现中，程序的递归过程要求每次进行分治计算，即带入式的大整数X和Y有如下要求：1X和Y的位数相同。2X和Y的位数是2的次幂。按照这样的限制，我们只能计算nn位（n=1,2,4,8,16.）的整数乘法。显然，这样的算法有很大的局限性，它不能处理像13212758这样更为普遍的问题。因此，我们在算法里采用这样的处理方法：当大整数需要进行分治乘法时，在两个乘数的高位补0，使它们的位数达到相同的2的次幂；分治结束后，将得到的乘积的高位多余的0去除，进行加减等非分治算法运算；以此类推。采用这种高位补0的位数处理方法，实现了任意位大整数的乘法。 除了上述三点之外，程序对鲁棒性做了增强，对非法输入和文件错误进行了检测。程序设计代码： /*头文件 大数乘法问题.h*/#ifndef KNAP_H#define KNAP_H#include #include #include using namespace std;/*定义数制，范围2到10*/#define SCALE 10/*整数的最大位数*/const int Max = 1000;/*表示整数的结构体*/struct Integerbool positive;/整数的正负short numMax;/整数的各位数字，下标从0开始int length;/整数的位数;/*两个整数的乘法类*/class Multiplypublic:Multiply(char *in, char *out);/构造函数Multiply();/析构函数void OutputProduct();/输出大整数的乘积protected:short CharToInt(char ch);/将数字字符转化成整型int AddDigit(Integer &X, Integer &Y); /将位数补充到相同2的次幂位void InitialInteger(Integer &integer, ifstream &in);/文件初始化大整数void OutputInteger(Integer integer);/输出大整数integervoid ClearZero(Integer &integer);/去除大整数高位多余的0bool PositiveXGreaterThanY(Integer X, Integer Y);/判断是否非负X大于非负Ybool EqualsToZero(Integer integer);/判断是否等于0Integer Zero();/返回大整数0Integer GetAbsolute(Integer integer);/返回大整数integer的绝对值Integer GetNegative(Integer integer);/返回大整数integer的负值Integer GetLeft(Integer integer);/取大整数integer左一半Integer GetRight(Integer integer);/取大整数integer右一半Integer LeftShifting(Integer integer, int digit);/大整数向左移digit位，低位补0Integer Plus(Integer X, Integer Y);/大整数加法Integer Subtract(Integer X, Integer Y);/大整数减法Integer SameSignPlus(Integer X, Integer Y);/同号大整数加法Integer SameSignSubtract(Integer X, Integer Y);/同号大整数减法Integer OneDigitMultiply(Integer X, Integer Y);/非负1位大整数乘法Integer FreeMultiply(Integer X, Integer Y);/任意大整数乘法Integer NDigitsMultiply(Integer X, Integer Y, int n);/2的n次幂乘法，高位补0private:Integer integer_X, integer_Y;/数组存储的大整数ofstream fout;/输出结果文件;#endif/*函数实现文件 大数乘法问题.cpp*/#include 大数乘法问题.hMultiply:Multiply(char *in, char *out) : fout(out)try/非法输入检测ifstream fin(in);if( !fin )throw 输入文件无法打开！n;InitialInteger(integer_X, fin);/文件初始化大整数integer_Xfin.ignore(100, n);/冲掉回车InitialInteger(integer_Y, fin);/文件初始化大整数integer_Yfin.close();/关闭文件if( !fout )throw 输出文件无法打开！n;catch(char *string)cout = SCALE)throw Error : 输入不符合数制！n;return temp;int Multiply:AddDigit(Integer &X, Integer &Y)int digit = 0;if(X.length Y.length)digit = X.length;elsedigit = Y.length;/取二者最大位数int i;for(i = 0; pow(2.0, i) = X.length; i-)X.numi = 0;for(i = digit-1; i = Y.length; i-)Y.numi = 0;/高位补0，使位数达到2的次幂X.length = Y.length = digit;/改变二者的位数return digit;/返回2的次幂void Multiply:InitialInteger(Integer &integer, ifstream &in)if(in.peek() = -)in.get();integer.positive = false;elseinteger.positive = true;int i;char tempMax;for(i = 0; in.peek() != n & !in.eof(); i+)/读到回车处或文件结束in tempi;integer.length = i;for(i = 0; i integer.length; i+)integer.numi = CharToInt(tempinteger.length - i - 1);/将每一位字符转化为整型void Multiply:OutputInteger(Integer integer)if(integer.length = 0)/结果为0fout integer.num0;elseif(integer.positive = false)/结果为负数fout -1; i-)fout = 0; i-)integer.length-;bool Multiply:PositiveXGreaterThanY(Integer X, Integer Y)if(X.length Y.length)/X位数大于Yreturn true;else if(X.length = 0; i-)/从高位逐位比较if(X.numi Y.numi)/某一位X大于Yreturn true;else if(X.numi = 0; i-)if(integer.numi != 0)return false;return true;Integer Multiply:Zero()Integer temp;temp.length = 0;/0的位数定义为0temp.positive = true;temp.num0 = 0;/0的第一位默认为0return temp;Integer Multiply:GetAbsolute(Integer integer)if(integer.positive = false)integer.positive = true;return integer;Integer Multiply:GetNegative(Integer integer)if(integer.positive = true)integer.positive = false;elseinteger.positive = true;return integer;Integer Multiply:GetLeft(Integer integer)Integer temp;temp.length = integer.length / 2;/位数为一半temp.positive = true;/默认是正数for(int i = 0; i temp.length; i+)/取原整数左一半temp.numi = integer.numi+temp.length;ClearZero(temp);/去除高位多余的0return temp;Integer Multiply:GetRight(Integer integer)Integer temp;temp.length = integer.length / 2;/位数为一半temp.positive = true;/默认是正数for(int i = 0; i = digit - 1; i-)integer.numi = integer.numi-digit;/原有位向高位移digit位for(int i = digit - 1; i = 0; i-)integer.numi = 0;/低位补0integer.length = integer.length + digit;/位数加digitreturn integer;Integer Multiply:Plus(Integer X, Integer Y)if(X.positive = Y.positive)/同号return SameSignPlus(X, Y);else/异号if(X.positive)/X正Y负Y = GetNegative(Y);/Y取负得正return SameSignSubtract(X, Y);else/Y正X负X = GetNegative(X);/X取负得正return SameSignSubtract(Y, X);Integer Multiply:Subtract(Integer X, Integer Y)if(X.positive = Y.positive)/同号return SameSignSubtract(X, Y);elseY = GetNegative(Y);/Y取负得正return SameSignPlus(X, Y);Integer Multiply:SameSignPlus(Integer X, Integer Y)int i;int carry_flag = 0;/进位for(i = 0; i X.length & i SCALE-1)/当为加法需要进位X.numi = (X.numi + Y.numi + carry_flag) % SCALE;carry_flag = 1;elseX.numi = X.numi + Y.numi + carry_flag;carry_flag = 0;if(i X.length)/被加数位数大于加数while(i SCALE-1)/需要进位X.numi+ = (X.numi + carry_flag) % SCALE;carry_flag = 1;elseX.numi+ = X.numi + carry_flag;carry_flag = 0;else if(i Y.length)/加数位数大于被加数while(i SCALE-1)/需要进位X.numi+ = (Y.numi + carry_flag) % SCALE;carry_flag = 1;elseX.numi+ = Y.numi + carry_flag;carry_flag = 0;if(carry_flag = 1)/最高位存在进位X.numi = 1;X.length = i+1;elseX.length = i;return X;Integer Multiply:SameSignSubtract(Integer X, Integer Y)if(PositiveXGreaterThanY(X, Y)/如果绝对值X=Yint i;int carry_flag = 0;/借位bool first_0 = true;/高位第一次出现0int top_digit_0 = 0;/记录结果最高位+1的下标int top_digit = 0;/记录结果最高位下标for(i = 0; i Y.length; i+)if(X.numi - carry_flag Y.numi)/需要向高位借位X.numi = (X.numi - carry_flag + SCALE - Y.numi);carry_flag = 1;elseX.numi = X.numi - carry_flag - Y.numi;carry_flag = 0;if(X.numi = 0)/高位出现0if(first_0)/且是第一次出现0first_0 = false;/再出现0则不是第一次出现0top_digit_0 = i;/记录结果最高位+1的下标elsefirst_0 = true;top_digit = i;if(carry_flag = 1)/最高位存在借位X.numi = X.numi - carry_flag;if(X.numi = 0 & first_0)top_digit_0 = i;if(top_digit top_digit)/top_digit_0=0表示没有改变X.length = top_digit_0;/调整结果的位数return X;else/如果XYX = SameSignSubtract(Y, X);/先用Y-XX = GetNegative(X);/再去负值return X;Integer Multiply:OneDigitMultiply(Integer X, Integer Y)Integer temp;temp.positive = true;int product;/乘积product = X.num0 * Y.num0;int i;for(i = 0; product != 0; i+)/存储到数组中temp.numi = product % SCALE;product /= SCALE;temp.length = i;return temp;Integer Multiply:FreeMultiply(Integer X, Integer Y)bool sign;/乘积符号if(X.positive = Y.positive)/同号sign = true;/乘积是正数else/同号sign = false;/乘积是负数X = GetAbsolute(X);Y = GetAbsolute(Y);/取两数绝对值if(EqualsToZero(X) | EqualsToZero(Y)/如果有0，乘积为0return Zero();Integer temp;if(X.length = 1 & Y.length = 1)/只剩1位乘法temp = OneDigitMultiply(X, Y);/返回1位乘积elseint n = AddDigit(X, Y);/X和Y位数补充到2的次幂位temp = NDigitsMultiply(X, Y, n);/分治法得到乘积temp.positive = sign;/赋符号return temp;/返回递