大整数乘法问题

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

大整数乘法问题 2.4 大整数乘法问题算法设计思想: (1) 大整数的存储我们知道，在编译系统中，整型数据类型的最大存储空间为8字节，也就是最大能 32308存储2的数据。即使使用双精度浮点数据类型(double)，也只能存储最大1.798×10 200的数据。如果需要计算10数量级的整数的乘法，利用的现有的数据类型就无法实现了。所以，为了实现大整数的乘法，需要自己定义一种数据类型，以及对应的基本运算。在该算法中，为了调试和处理方便，我们采用静态整型数组来存放大整数，即用数组的每一个元素存放大整数一位上的数字。然后，分别定义用数组存放的大整数的加法、减法和移位运算。这样，我们就可以用定义的大整数进行后面分治乘法的运算。 (2) 分治思想将位数是2的次幂的n位的十进制大整数X和Y各分为2段，每段的长为n/2位。 n/2n/2则有，X=A×10+B ，Y=C×10+D。这样，乘积问题变为这样的分治问题: n/2n/2nn/2 XY=(A×10+B)(C×10+D)=AC×10+(AD+CB)×10+BD ? 2如果按?式计算XY，我们可得时间复杂度T(n)=O(n)(详细论证在课本上)。显然，用?式来计算X和Y的乘积并不比乘法竖式更有效。为了改进算法的计算复杂性，我们把XY写成另一种形式: nn/2 XY=AC×10+[(A-B)(D-C)+AC+BD]×10+BD ? log31.59用解递归方程的套用公式法可得?式的时间复杂度T(n)=O(n)=O(n)，该结果有效地减小了算法的时间复杂度。因此，根据?式，我们得到了大整数相乘的分治算法。 (3) 高位补0的位数处理方法我们提出的分治思想在理论上是可行的，但是在算法具体实现中，程序的递归过程要求每次进行分治计算，即带入?式的大整数X和Y有如下要求: 1(X和Y的位数相同。 2(X和Y的位数是2的次幂。按照这样的限制，我们只能计算n×n位(n=1,2,4,8,16...)的整数乘法。显然，这样的算法有很大的局限性，它不能处理像132×12758这样更为普遍的问题。因此，我们在算法里采用这样的处理方法:当大整数需要进行分治乘法时，在两个乘数的高位补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 Integer { bool positive; //整数的正负 short num[Max]; //整数的各位数字，下标从0开始 int length; //整数的位数 }; /*两个整数的乘法类*/ class Multiply { public: 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); //输出大整数integer void ClearZero(Integer &integer); //去除大整数高位多余的0 bool PositiveXGreaterThanY(Integer X, Integer Y); //判断是否非负X大于非负Y bool EqualsToZero(Integer integer); //判断是否等于0 Integer Zero(); //返回大整数0 Integer 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位，低位补0 Integer 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次幂乘法，高位补0 private: Integer integer_X, integer_Y; //数组存储的大整数 ofstream fout; //输出结果文件 }; #endif /*函数实现文件大数乘法问题.cpp*/ #include "大数乘法问题.h" Multiply::Multiply(char *in, char *out) : fout(out) { try //非法输入检测 { ifstream fin(in); if( !fin ) throw "输入文件无法打开～\n"; InitialInteger(integer_X, fin); //文件初始化大整数integer_X fin.ignore(100, '\n'); //冲掉回车 InitialInteger(integer_Y, fin); //文件初始化大整数integer_Y fin.close(); //关闭文件 if( !fout ) throw "输出文件无法打开～\n"; } catch(char *string) { cout << string; system("pause"); exit(0); } } Multiply::~Multiply() { if(fout) fout.close(); } void Multiply::OutputProduct() { Integer temp = FreeMultiply(integer_X, integer_Y); ClearZero(temp); OutputInteger(temp); } short Multiply::CharToInt(char ch) { short temp; switch(ch) { case '0' : temp = 0; break; case '1' : temp = 1; break; case '2' : temp = 2; break; case '3' : temp = 3; break; case '4' : temp = 4; break; case '5' : temp = 5; break; case '6' : temp = 6; break; case '7' : temp = 7; break; case '8' : temp = 8; break; case '9' : temp = 9; break; default : temp = -1; break; } if(temp == -1) throw "Error : 输入存在非数字字符～\n"; if(temp >= SCALE) throw "Error : 输入不符合数制～\n"; return temp; } int Multiply::AddDigit(Integer &X, Integer &Y) { int digit = 0; if(X.length > Y.length) digit = X.length; else digit = Y.length; //取二者最大位数 int i; for(i = 0; pow(2.0, i) < digit; i++); digit = (int)pow(2.0, i); //取满足二者的最小2的次幂 for(i = digit-1; i >= X.length; i--) X.num[i] = 0; for(i = digit-1; i >= Y.length; i--) Y.num[i] = 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; } else integer.positive = true; int i; char temp[Max]; for(i = 0; in.peek() != '\n' && !in.eof(); i++) //读到回车处或文件结束 in >> temp[i]; integer.length = i; for(i = 0; i < integer.length; i++) integer.num[i] = CharToInt(temp[integer.length - i - 1]);//将每一位字符转化为整型 } void Multiply::OutputInteger(Integer integer) { if(integer.length == 0) //结果为0 fout << integer.num[0]; else { if(integer.positive == false) //结果为负数 fout << '-'; for(int i = integer.length - 1; i > -1; i--) fout << integer.num[i]; } } void Multiply::ClearZero(Integer &integer) { for(int i = integer.length-1; integer.num[i] == 0 && i >= 0; i--) integer.length--; } bool Multiply::PositiveXGreaterThanY(Integer X, Integer Y) { if(X.length > Y.length) //X位数大于Y return true; else if(X.length < Y.length) //X位数小于Y return false; else for(int i = X.length-1; i >= 0; i--) //从高位逐位比较 if(X.num[i] > Y.num[i]) //某一位X大于Y return true; else if(X.num[i] < Y.num[i]) //某一位X小于Y return false; return true; //X=Y返回true } bool Multiply::EqualsToZero(Integer integer) { for(int i = integer.length-1; i >= 0; i--) if(integer.num[i] != 0) return false; return true; } Integer Multiply::Zero() { Integer temp; temp.length = 0; //0的位数定义为0 temp.positive = true; temp.num[0] = 0; //0的第一位默认为0 return 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; else integer.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.num[i] = integer.num[i+temp.length]; ClearZero(temp); //去除高位多余的0 return temp; } Integer Multiply::GetRight(Integer integer) { Integer temp; temp.length = integer.length / 2; //位数为一半 temp.positive = true; //默认是正数 for(int i = 0; i < temp.length; i++) //取原整数右一半 temp.num[i] = integer.num[i]; ClearZero(temp); //去除高位多余的0 return temp; } Integer Multiply::LeftShifting(Integer integer, int digit) { if(!EqualsToZero(integer)) { for(int i = integer.length + digit - 1; i >= digit - 1; i--) integer.num[i] = integer.num[i-digit]; //原有位向高位移digit位 for(int i = digit - 1; i >= 0; i--) integer.num[i] = 0; //低位补0 integer.length = integer.length + digit; //位数加digit } return 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); else { Y = 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 < Y.length; i++) { if(X.num[i] + Y.num[i] + carry_flag > SCALE-1) //当为加法需要进位 { X.num[i] = (X.num[i] + Y.num[i] + carry_flag) % SCALE; carry_flag = 1; } else { X.num[i] = X.num[i] + Y.num[i] + carry_flag; carry_flag = 0; } } if(i < X.length) //被加数位数大于加数 { while(i < X.length) { if(X.num[i] + carry_flag > SCALE-1) //需要进位 { X.num[i++] = (X.num[i] + carry_flag) % SCALE; carry_flag = 1; } else { X.num[i++] = X.num[i] + carry_flag; carry_flag = 0; } } } else if(i < Y.length) //加数位数大于被加数 { while(i < Y.length) { if(Y.num[i] + carry_flag > SCALE-1) //需要进位 { X.num[i++] = (Y.num[i] + carry_flag) % SCALE; carry_flag = 1; } else { X.num[i++] = Y.num[i] + carry_flag; carry_flag = 0; } } } if(carry_flag == 1) //最高位存在进位 { X.num[i] = 1; X.length = i+1; } else { X.length = i; } return X; } Integer Multiply::SameSignSubtract(Integer X, Integer Y) { if(PositiveXGreaterThanY(X, Y)) //如果绝对值X>=Y { int i; int carry_flag = 0; //借位 bool first_0 = true; //高位第一次出现0 int top_digit_0 = 0; //记录结果最高位+1的下标 int top_digit = 0; //记录结果最高位下标 for(i = 0; i < Y.length; i++) { if(X.num[i] - carry_flag < Y.num[i]) //需要向高位借位 { X.num[i] = (X.num[i] - carry_flag + SCALE - Y.num[i]); carry_flag = 1; } else { X.num[i] = X.num[i] - carry_flag - Y.num[i]; carry_flag = 0; } if(X.num[i] == 0) //高位出现0 { if(first_0) //且是第一次出现0 { first_0 = false; //再出现0则不是第一次出现0 top_digit_0 = i; //记录结果最高位+1的下标 } } else { first_0 = true; top_digit = i; } } if(carry_flag == 1) //最高位存在借位 { X.num[i] = X.num[i] - carry_flag; if(X.num[i] == 0 && first_0) top_digit_0 = i; } if(top_digit < X.length - 1) //如果被减数更高位还有数字 top_digit = X.length; if(top_digit_0 && top_digit_0 > top_digit) //top_digit_0==0表示没有改变 X.length = top_digit_0; //调整结果的位数 return X; } else //如果X

                    本文档为【大整数乘法问题】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
                    图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。 
 该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。

                    [版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。

                    本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。

                    网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
                

下载需要：免费已有0 人下载

立即下载

大整数乘法问题

你可能还喜欢