大整数基本运算的实现研究与分析.doc

目录目录11设计要求22开发环境与工具23设计原理（算法工作原理）24系统功能描述与软件模块划分25设计核心代码.3 6设计结果及验证7 7软件使用说明78参考资料99设计体会.910源代码.10一、设计要求1. 实现大整数（ 128位）的基本运算、如加、减、乘、除运算；2. 实现大整数的存取；3. 界面简洁、交互操作性强。二、开发环境与工具Windows 8.1 、visual studio 20123、 设计原理（算法工作原理）大整数的概念“大整数”一般指位数达到十几或成百上千甚至更多的整数，而更准确地说，应该是指普通程序设计语言中的整数类型值集范围以上的整数。如标准的C的Unsigned long 型整数所能处理的整数范围最大，有效数位也最多，为4294967295()占据32 位（4 个字节）存贮空间，此时，大整数就是指十位以上的十进制整数了。“大整数”运算是指“大整数”之间的加减乘除等运算结果依然保持其数学理论上准确和精确的结果。我们采用数组存储的方式存储，并且存储的位数不能大于256位，否则会发生溢出错误而导致大整数处理错误。对于负数，程序将不能处理，可以输入，计算结果输出为整数。4、 系统功能描述与软件模块划分 相关函数介绍void hadd(int *xx1,int *xx2,int *xx3,int xn1,int xn2,int &xn3) /*加法操作*/ void hsub(int *xx1,int *xx2,int *xx3,int xn1,int xn2,int &xn3) /*减法操作*/ void hmul(int *xx1,int *xx2,int xn1,int &xn2,int xn) /*乘法操作*/ int hdiv(int *xx1,int *xx2,int *xx3,int xn1,int xn2,int &xn3) /*除法操作*/ void show(int); /显示5、 设计核心代码1、加法在大整数四则运算中，加法是基本的运算，也最容易实现。void hadd(int *xx1,int *xx2,int *xx3,int xn1,int xn2,int &xn3) / /*加法操作*/ int i,j,k=0; if(xn1xn2) xn3=xn1; /xn3为过渡位，都表示最大位数 for(i=0;ixn1-xn2;i+) xx2Max-xn3+i=0; /对小数xx2高位填充0，直至位数相等 else xn3=xn2; for(i=0;ixn2-xn1;i+) xx1Max-xn3+i=0; /*把短的字符串前补0*/ for(i=0;i=1) /有进位且结果未满256 xx3Max-1-xn3=k; /将结果填满xn3+; /*增加一位存放最高位*/ void larnum:add(void) hadd(x1,x2,x3,n1,n2,n3); 2、减法void hsub(int *xx1,int *xx2,int *xx3,int xn1,int xn2,int &xn3) / /*减法操作*/ int i,j,k=0; xn3=xn1; /将被减数位数付给结果的位数for(i=0;ixn1-xn2;i+) xx2Max-xn3+i=0; /将减数的高位用0从左到右补齐for(i=0;i=0) k=0; /不进位，减下来的值就给xx3xx3Max-1-i=j; else k=1; /否则进一位，左边的高位加上10xx3Max-1-i=j+10; for(i=0;ixn3-1&xx3Max-xn3+i=0;i+);/判断最后答案xn3的长度，高位为0，就长度减一xn3-=i; void larnum:sub(void) hsub(x1,x2,x3,n1,n2,n3); 3、乘法void hmul(int *xx1,int *xx2,int xn1,int &xn2,int xn) / /*乘法操作*/ int i,j,k=0; for(i=0;i=1) /有进位且结果的位数无溢出 xx2Max-1-xn2=k; /从低位将结果补满xn2+; for(i=0;ixn2-1&xx2Max-xn2+i=0;i+); /判断最后答案xn2长度，高位为0，就长度减一xn2-=i; void larnum:mul(void) /larnum的成员mul(),进行乘法运算 int i,j,k,xMax,xn,yMax,yn=0; for(i=0;in2;i+) hmul(x1,x,n1,xn,x2Max-1-i); /调用私有成员函数hmul() xn为结果的长度for(j=0;j=1);j+) /因为是大整数相乘，会有多次的两数相乘乘积得到的值 for(k=0;kxn;k+) xMax-1-xn+k=xMax-xn+k; xMax-1=0; xn+; hadd(x,y,x3,xn,yn,n3); for(j=0;jn3;j+) yMax-1-j=x3Max-1-j; /多次的两数相乘乘积得到的值进行加法运算yn=n3; for(i=0;ixn2) /被除数除数的情况k=0; /k=0else if(xn1=xn2) for(i=0,k=2;ixx2Max-xn1+i) /比较同长度的数最高位，标志位为0不变，正常的除法情况 k=0; break; else if(xx1Max-xn1+ixx2Max-xn1+i)/否则要标志位置1 k=1; break; else k=1; if(k=1) /如果是同长高位12,或者长度1长度2 56/66 6/66 for(i=0;i2 6?/5? hsub(xx1,xx2,xx3,xn1,xn2,xn3); /调用上面的hsub函数，此时就相当于减法操作了，因为商唯一，得出余数return k; int larnum:div(void) int xMax,xn=0,i,j,k,n; if(n2=0|(n2=1&x2Max-1=0) /判断输入的数是否合法，除数为0报错 couterror.除数不能为0 !endl; return 1; for(i=0,n3=n1;in1;i+) /还是开始循环调用上面的hdiv()函数，且多次调用 for(j=0;jxn;j+) /和上面的hdiv()一样讨论被除数和除数的情况，求值xMax-1-xn+j=xMax-xn+j; xMax-1=x1Max-n1+i; xn+; k=hdiv(x,x2,x4,xn,n2,n4); if(k=2) x3Max-n1+i=1; else if(k=1) x3Max-n1+i=0; else for(n=1;n+) for(j=0;jn4;j+) xMax-1-j=x4Max-1-j; xn=n4; k=hdiv(x,x2,x4,xn,n2,n4); if(k=1) break; x3Max-n1+i=n; for(j=0;jn4;j+) /从低位开始，将x4数值赋给x，作为余数xMax-1-j=x4Max-1-j; /长度也进行赋值xn=n4; for(i=0;in3-1&x3Max-n3+i=0;i+); /判断最后答案n3的长度，高位为0，就长度减一n3-=i; for(i=0;in4-1&x4Max-n4+i=0;i+); /判断最后余数n4长度，高位为0，就长度减一n4-=i; return 0; 六、设计结果及验证以下是我本次设计软件的使用，以及使用成功的截图。7、 软件使用说明选择一，然后输入两个大整数，进行加法运算，结果如下：选择二，然后输入两个大整数，进行减法运算，结果如下：选择三，然后输入两个大整数，进行乘法运算，结果如下：选择四，然后输入两个大整数，进行除法运算，结果如下：#include #include using namespace std; #define Max 256 /* 定义数组大小为256，以至能实现128位大整数的乘法 */ class larnum public:void add(void); void sub(void); void mul(void); int div(void); larnum(char *,char *); void show(int); private: int x1Max; int x2Max; int x3Max; intx4Max; int n1; int n2; int n3; int n4; void hadd(int *xx1,int *xx2,int *xx3,int xn1,int xn2,int &xn3) / /*加法操作*/ int i,j,k=0; if(xn1xn2) xn3=xn1; /xn3为过渡位，都表示最大位数 for(i=0;ixn1-xn2;i+) xx2Max-xn3+i=0; /对小数xx2高位填充0，直至位数相等 else xn3=xn2; for(i=0;ixn2-xn1;i+) xx1Max-xn3+i=0; /*把短的字符串前补0*/ for(i=0;i=1) /有进位且结果未满256 xx3Max-1-xn3=k; /将结果填满xn3+; /*增加一位存放最高位*/ void hsub(int *xx1,int *xx2,int *xx3,int xn1,int xn2,int &xn3) / /*减法操作*/ int i,j,k=0; xn3=xn1; /将被减数位数付给结果的位数for(i=0;ixn1-xn2;i+) xx2Max-xn3+i=0; /将减数的高位用0从左到右补齐for(i=0;i=0) k=0; /不进位，减下来的值就给xx3xx3Max-1-i=j; else k=1; /否则进一位，左边的高位加上10xx3Max-1-i=j+10; for(i=0;ixn3-1&xx3Max-xn3+i=0;i+);/判断最后答案xn3的长度，高位为0，就长度减一xn3-=i; void hmul(int *xx1,int *xx2,int xn1,int &xn2,int xn) / /*乘法操作*/ int i,j,k=0; for(i=0;i=1) /有进位且结果的位数无溢出 xx2Max-1-xn2=k; /从低位将结果补满xn2+; for(i=0;ixn2) /被除数除数的情况k=0; /k=0else if(xn1=xn2) for(i=0,k=2;ixx2Max-xn1+i) /比较同长度的数最高位，标志位为0不变，正常的除法情况 k=0; break; else if(xx1Max-xn1+ixx2Max-xn1+i)/否则要标志位置1 k=1; break; else k=1; if(k=1) /如果是同长高位12,或者长度1长度2 56/66 6/66 for(i=0;i2 6?/5? hsub(xx1,xx2,xx3,xn1,xn2,xn3); /调用上面的hsub函数，此时就相当于减法操作了，因为商唯一，得出余数return k; ; larnum:larnum(char *y1=0,char *y2=0) int i; for(n1=0;n1=0&y1n1=9;n1+); /用n1表示输入的第一个数满足在0-9之间，就接受 for(i=0;in1;i+) /循环将y1里面的数将数字从gao位开始放进x1x1Max-n1+i=*(y1+i)-48; for(i=0;in1-1&x1Max-n1+i=0;i+); / 循环判断数字的高位是否为0,为0，则相应的减去一位n1-=i; for(n2=0;n2=0&y2n2=9;n2+); /用n2表示输入的第一个数满足在0-9之间，就接受for(i=0;in2;i+) /循环将y2里面的数将数字从gao位开始放进x2x2Max-n2+i=*(y2+i)-48; for(i=0;in2-1&x2Max-n2+i=0;i+); / 循环判断数字的高位是否为0,为0，则相应的减去一位 n2-=i; /void larnum:add(void) / larnum的成员add(),加法直接调用加法hadd() hadd(x1,x2,x3,n1,n2,n3); void larnum:sub(void) /larnum的成员sub(),减法直接调用减法hsub() hsub(x1,x2,x3,n1,n2,n3); /void larnum:mul(void) /larnum的成员mul(),进行乘法运算 int i,j,k,xMax,xn,yMax,yn=0; for(i=0;in2;i+) hmul(x1,x,n1,xn,x2Max-1-i); /调用私有成员函数hmul() xn为结果的长度for(j=0;j=1);j+) /因为是大整数相乘，会有多次的两数相乘乘积得到的值 for(k=0;kxn;k+) xMax-1-xn+k=xMax-xn+k; xMax-1=0; xn+; hadd(x,y,x3,xn,yn,n3); for(j=0;jn3;j+) yMax-1-j=x3Max-1-j; /多次的两数相乘乘积得到的值进行加法运算yn=n3; for(i=0;in3-1&x3Max-n3+i=0;i+); /判断最后答案xn3的长度，高位为0，就长度减一n3-=i; / int larnum:div(void) int xMax,xn=0,i,j,k,n; if(n2=0|(n2=1&x2Max-1=0) /判断输入的数是否合法，除数为0报错 couterror.除数不能为0 !endl; return 1; for(i=0,n3=n1;in1;i+) /还是开始循环调用上面的hdiv()函数，且多次调用 for(j=0;jxn;j+) /和上面的hdiv()一样讨论被除数和除数的情况，求值xMax-1-xn+j=xMax-xn+j; xMax-1=x1Max-n1+i; xn+; k=hdiv(x,x2,x4,xn,n2,n4); if(k=2) x3Max-n1+i=1; else if(k=1) x3Max-n1+i=0; else for(n=1;n+) for(j=0;jn4;j+) xMax-1-j=x4Max-1-j; xn=n4; k=hdiv(x,x2,x4,xn,n2,n4); if(k=1) break; x3Max-n1+i=n; for(j=0;jn4;j+) /从低位开始，将x4数值赋给x，作为余数xMax-1-j=x4Max-1-j; /长度也进行赋值xn=n4; for(i=0;in3-1&x3Max-n3+i=0;i+); /判断最后答案n3的长度，高位为0，就长度减一n3-=i; for(i=0;in4-1&x4Max-n4+i=0;i+); /判断最后余数n4长度，高位为0，就长度减一n4-=i; return 0; / void larnum:show(int k) /输出结果，有余数输出余数操作 int i; for(i=0;in3;i+) coutx3Max-n3+i; if(k) coutendl; cout余数为:endl; for(i=0;in4;i+) coutx4Max-n4+i; coutendl; /*用k控制余数的输出*/ int main() while(1) char s1Max,s2Max; int k; int choose; cout1.大整数的加法运算.endl; cout2.大整数的减法运算.endl; cout3.大整数的乘法运算.endl; cout4.大整数的除法运算.endl; cout5.退出.endl;coutchoose; if(choose5) couts1;couts2; larnum A(s1,s2); if(choose=1) cout加法运算结果为:endl; A.add(); A.show(0); coutendlendlendl; else if(choose=2) cout减法运算结果为:endl; A.sub(); A.show(0); coutendlendlendl; else if(choose=3) cout乘法运算结果为:endl; A.mul(); A.show(0); coutendlendlendl; else cout除法运算结果为:endl; k=A.div(); if(!k) A.show(1); coutendlendlendl; else break; return 0; #include #include using namespace std; #define Max 256 /* 定义数组大小为256，以至能实现128位大整数的乘法 */ class larnum public:void add(void); void sub(void); void mul(void); int div(void); larnum(char *,char *); void show(int); private: int x1Max; int x2Max; int x3Max; intx4Max; int n1; int n2; int n3; int n4; void hadd(int *xx1,int *xx2,int *xx3,int xn1,int xn2,int &xn3) / /*加法操作*/ int i,j,k=0; if(xn1xn2) xn3=xn1; /xn3为过渡位，都表示最大位数 for(i=0;ixn1-xn2;i+) xx2Max-xn3+i=0; /对小数xx2高位填充0，直至位数相等 else xn3=xn2; for(i=0;ixn2-xn1;i+) xx1Max-xn3+i=0; /*把短的字符串前补0*/ for(i=0;i=1) /有进位且结果未满256 xx3Max-1-xn3=k; /将结果填满xn3+; /*增加一位存放最高位*/ void hsub(int *xx1,int *xx2,int *xx3,int xn1,int xn2,int &xn3) / /*减法操作*/ int i,j,k=0; xn3=xn1; /将被减数位数付给结果的位数for(i=0;ixn1-xn2;i+) xx2Max-xn3+i=0; /将减数的高位用0从左到右补齐for(i=0;i=0) k=0; /不进位，减下来的值就给xx3xx3Max-1-i=j; else k=1; /否则进一位，左边的高位加上10xx3Max-1-i=j+10; for(i=0;ixn3-1&xx3Max-xn3+i=0;i+);/判断最后答案xn3的长度，高位为0，就长度减一xn3-=i; void hmul(int *xx1,int *xx2,int xn1,int &xn2,int xn) / /*乘法操作*/ int i,j,k=0; for(i=0;i=1) /有进位且结果的位数无溢出 xx2Max-1-xn2=k; /从低位将结果补满xn2+; for(i=0;ixn2) /被除数除数的情况k=0; /k=0else if(xn1=xn2) for(i=0,k=2;ixx2Max-xn1+i) /比较同长度的数最高位，标志位为0不变，正常的除法情况 k=0; break; else if(xx1Max-xn1+ixx2Max-xn1+i)/否则要标志位置1 k=1; break; else k=1; if(k=1) /如果是同长高位12,或者长度1长度2 56/66 6/66 for(i=0;i2 6?/5? hsub(xx1,xx2,xx3,xn1,xn2,xn3); /调用上面的hsub函数，此时就相当于减法操作了，因为商唯一，得出余数return k; ; larnum:larnum(char *y1=0,char *y2=0) int i; for(n1=0;n1=0&y1n1=9;n1+); /用n1表示输入的第一个数满足在0-9之间，就接受 for(i=0;in1;i+) /循环将y1里面的数将数字从gao位开始放进x1x1Max-n1+i=*(y1+i)-48; for(i=0;in1-1&x1Max-n1+i=0;i+); / 循环判断数字的高位是否为0,为0，则相应的减去一位n1-=i; for(n2=0;n2=0&y2n2=9;n2+); /用n2表示输入的第一个数满足在0-9之间，就接受for(i=0;in2;i+) /循环将y2里面的数将数字从gao位开始放进x2x2Max-n2+i=*(y2+i)-48; for(i=0;in2-1&x2Max-n2+i=0;i+); / 循环判断数字的高位是否为0,为0，则相应的减去一位 n2-=i; /void larnum:add(void) / larnum的成员add(),加法直接调用加法hadd() hadd(x1,x2,x3,n1,n2,n3); void larnum:sub(void) /larnum的成员sub(),减法直接调用减法hsub() hsub(x1,x2,x3,n1,n2,n3); /void larnum:mul(void) /larnum的成员mul(),进行乘法运算 int i,j,k,xMax,xn,yMax,yn=0; for(i=0;in2;i+) hmul(x1,x,n1,xn,x2Max-1-i); /调用私有成员函数hmul() xn为结果的长度for(j=0;j=1);j+) /因为是大整数相乘，会有多次的两数相乘乘积得到的值 for(k=0;kxn;k+) xMax-1-xn+k=xMax-xn+k; xMax-1=0; xn+; hadd(x,y,x3,xn,yn,n3); for(j=0;jn3;j+) yMax-1-j=x3Max-1-j; /多次的两数相乘乘积得到的值进行加法运算yn=n3; for(i=0;in3-1&x3Max-n3+i=0;i+); /判断最后答案xn3的长度，高位为0，就长度减一n3-=i; / int larnum:div(void) int xMax,xn=0,i,j,k,n; if(n2=0|(n2=1&x2Max-1=0) /判断输入的数是否合法，除数为0报错 couterror.除数不能为0 !endl; return 1; for(i=0,n3=n1;in1;i+) /还是开始循环调用上面的hdiv()函数，且多次调用 for(j=0;jxn;j+) /和上面的hdiv()一样讨论被除数和