大整数运算

大整数运算 数据结构课程设计 大整数运算的实现 计算机科学学院计算机5班 09XXXXXXX46 XX 2100-04-20 1 一、需求分析 1、课程要求 A(实现大整数的基本运算 B(提供友好的用户界面 C(对于异常的表达式能给出出错提示 2、设计目标 A(软件名称:大整数运算器 B(软件组成:大整数源码.cpp C(制作平台及相关调试工具:Microsoft Visual C++6.0 D(运行环境:dos/win98/winMe/win2K/winxp/Win7 E(性能特点:1.当用户输入一个合法的算术表达式后，能够返回正确的结果 2.能够进行加、减、乘三种运算 3.对于异常表达式能够出错误提示 4.能显示运算时间 二、设计概要 1.相关函数介绍 1. void main()/////主函数///// 2. void add(orderstack &integer1,orderstack &integer2,orderstack &integer3) ///// 加法函数///// 3. void reduce(orderstack &integer1,orderstack &integer2,orderstack &integer3) /////减法函数///// 4. void multiply(orderstack& integer1,orderstack& integer2,orderstack& integer3) /////乘法函数/////模拟乘法竖式算法///// 5. void input(orderstack &integer1,orderstack &integer2)////输入函数///// 6. int menu()/////菜单函数///// 7. int compare(orderstack integer1,orderstack integer2) /////比较大小函数///// 按位比较///// 8. int convert(char x) /////类型转换函数-将字符型转换成整型///// 2. 用户界面流程 2 选择需要的运算功能 加法 减法 乘法 初始化 list1 list2 初始化 list1 list2 初始化 list1 list2 输入数据至list1 list2 输入数据至list1 list2 输入数据至list1 list2 加法运算 减法运算 乘法运算 输出结果 输出结果 输出结果 判断是否要再次运算 Y N 退出结束 三、详细设计 1、大整数的表示 在32位字长的系统里，基本数据类型有: 8位数，BYTE，单字节:char，unsigned char。 16位数，WORD，字:short，unsigned short。 32位数，DWORD，双字:int，unsigned int。 64位数，QWORD，四字:__int64, unsigned __int64 这些基本数据类型的运算可以被机器指令所直接支持。 在x86平台上，多个字节的数据存放顺序是，低位数据存放在低位地址。 比如，0x00010203, 在内存中的存放顺序是 03，02，01，00。 照此类推，128位整数，8字，16字节，0x000102030405060708090A0B0C0D0E0F 的内存映像是:0F， 0E，0D，0C，0B，0A，09，08，07，06，05，04，03，02，01，00。 位数是2的整数次方，64位，128位，256位等整数，我们称之为规范整数。 3 进行大整数的四则运算的时候，一个基本的原理就是把大整数运算降解为32位四则运算的复合运算。降解的方式可以是位数减半，即256位降解为128位，128位降解为64位，直到降解为机器指令支持范围内的整数。这样的降解过程用到的所有的中间变量都是规范的整数。也可以是从高到低，每次降解32位。这样的话在降解过程中我们会使用到256-32=224，224-32=192，192-32=160等长度不等于2的整数次方的整数，我们称之为不规范的整数。减半降解运算过程比较容易理解，而逐次降解则会获得较好的性能。 大整数的符号。一般来说，大整数运算中，负数的使用是非常少的。如果要使用符号的话，同基本数据一样，最高位表示符号，剩余的数位用来表示有效值。 2、大整数加法 1.2.0 在大整数四则运算中，加法是基本的运算，也最容易实现。只要处理好进位数据就可以了。 LX_RESULT large_int_add_c32( BYTE* psa,BYTE* psb,BYTE* psd,DWORD* pca,int nBytes ) 返回值:LX_OK 输入参数:psa, 存放第一个操作数的地址。 输入参数:psb，第二个操作数的地址。 输出参数:psd，存放运算结果的地址。 输出参数:pca，存放进位数据的32位无符号整数地址。 输入参数:nBytes，大整数字节数。 ******************************************************************************/ LX_RESULT large_int_add_c32( BYTE* psa,BYTE* psb,BYTE* psd,DWORD* pca,int nBytes ) { int i; DWORD dwA; DWORD dwB; DWORD dwC = 0; DWORD* pwa = (DWORD*)psa; DWORD* pwb = (DWORD*)psb; DWORD* pwd = (DWORD*)psd; for( i = 0; i < nBytes ; i += 4 ) { ULARGE_INTEGER uld; dwA = *pwa++; // 取第一个操作数DWORD; dwB = *pwb++; // 取第二个操作数DWORD; uld.QuadPart = (__int64)dwA + dwB + dwC; // 带进位加; *pwd++ = (DWORD)( uld.LowPart); // 低32位输出; dwC = (DWORD)(uld.HighPart); // 高32位为进位; } *pca = dwC; // 输出进位; 4 return LX_OK; } 3、大整数减法 减法在大整数运算里面需要加以注意。 减法是通过把操作数取反并加1，然后做加法实现的。 在使用中应当避免小减大的情况。如果出现了这种情况，判断结果的最高位，如果是1， 结果清零，或者当作负数继续使用。 void large_int_not(BYTE* psa,int nBytes) 大整数取反运算。 void large_int_not(BYTE* psa,int nBytes) { for( int i = 0; i < nBytes; i += 4 ) { DWORD *ps = (DWORD*)(psa+i); *ps = ~*ps; } } int large_int_reverse(BYTE* psa,int nBytes) 大整数取反并加1。相当于改变符号。 int large_int_reverse(BYTE* psa,int nBytes) { DWORD dwCarry; large_int_not( psa , nBytes ); return large_int_add_pass_c32( psa, 1, psa, &dwCarry, nBytes ); } //LX_RESULT large_int_sub_c32( //BYTE* psa,BYTE* psb,BYTE* psd,DWORD* pca,int nBytes ) *****************************************************************************/ LX_RESULT large_int_sub_c32( BYTE* psa,BYTE* psb,BYTE* psd,DWORD* pca,int nBytes ) { BYTE* tmp = (BYTE*)xlivAlloc(nBytes,TRUE); if( !tmp ) { return LX_FAIL; } memcpy(tmp,psb,nBytes); large_int_reverse(tmp,nBytes); if( LX_OK != large_int_add_c32(psa,tmp,psd,pca,nBytes) ) { return LX_FAIL; } 5 if( tmp ) { xlivFree(tmp); } return LX_OK; } 4、大整数乘法 减半降解法。 设A，B是2n位的整数，A1,A0,B1,B0分别是A，B的高低n位。 A = A1<< n + A0; B = B1<> 1; BYTE* psa0 = (BYTE*)xlivAlloc(nDoubleSize,TRUE); BYTE* psb0 = (BYTE*)xlivAlloc(nDoubleSize,TRUE); BYTE* psd0 = (BYTE*)xlivAlloc(nDoubleSize,TRUE); BYTE* psa1 = (BYTE*)xlivAlloc(nDoubleSize,TRUE); BYTE* psb1 = (BYTE*)xlivAlloc(nDoubleSize,TRUE); BYTE* psd1 = (BYTE*)xlivAlloc(nDoubleSize,TRUE); BYTE* psdd = (BYTE*)xlivAlloc(nDoubleSize,TRUE); if( !psa0 || !psb0 || !psd0 || !psa1 || !psb1 || !psd1 || !psdd ) { nRe = LX_FAIL; goto fail; } memcpy(psa0,psa,nHalfSize); memcpy(psa1,psa+nHalfSize,nHalfSize); memcpy(psb0,psb,nHalfSize); memcpy(psb1,psb+nHalfSize,nHalfSize); large_int_mul_half_i(psa0,psb0,psd0,nHalfSize); large_int_mul_half_i(psa1,psb0,psd1,nHalfSize); large_int_shift_c32(psd1,-nHalfSize*8,psd1,nDoubleSize); large_int_add_c32(psd1,psd0,psdd,&dwCarry,nDoubleSize); // dwCarry must be zero; large_int_mul_half_i(psa0,psb1,psd0,nHalfSize); large_int_mul_half_i(psa1,psb1,psd1,nHalfSize); large_int_shift_c32(psd1,-nHalfSize*8,psd1,nDoubleSize); large_int_add_c32(psd1,psd0,psd1,&dwCarry,nDoubleSize); // dwCarry must be zero; large_int_shift_c32(psd1,-nHalfSize*8,psd1,nDoubleSize); large_int_add_c32(psd1,psdd,psd,&dwCarry,nDoubleSize); fail: if( psa0 ) { xlivFree(psa0); } if( psb0 ) { xlivFree(psb0); } if( psd0 ) { xlivFree(psd0); } if( psa1 ) { xlivFree(psa1); } if( psb1 ) { xlivFree(psb1); } if( psd1 ) { xlivFree(psd1); } if( psdd ) { xlivFree(psdd); } return nRe; } 然后我们用一个看来很简单的实现来调用上面的递归函数。 7 int large_int_mul_half( BYTE* psa,BYTE* psb,BYTE* psd,BYTE* pca,int nBytes ) { LX_RESULT nRe = LX_OK; BYTE* tmp = (BYTE*)xlivAlloc(nBytes*2,TRUE ); if( !tmp ) { nRe = LX_FAIL; goto fail; } nRe = large_int_mul_half_i(psa,psb,tmp,nBytes); if( LX_OK == nRe ) { memcpy(psd,tmp,nBytes); memcpy(pca,tmp+nBytes,nBytes); } fail: if( tmp ) { xlivFree(tmp); } return nRe; } 减半降解法的思路看来很清晰明了，结果也是正确的。但是很不幸，同后面我们使用的逐次降解法相比，计算速度低了一个数量级以上: //减半降解benchmark : 83 //逐次降解benchmark : 5072 大整数乘大整数 int large_int_mul_c32( BYTE* psa,BYTE* psb,BYTE* psd,BYTE* pca,int nBytes ) 返回值:LX_OK 输入参数:psa, 存放第一个操作数的地址。 输入参数:psb，存放第二个操作数的地址。 输出参数:psd，存放运算结果的地址。 输出参数:pca，存放高nBytes字节的内存地址。 输入参数:nBytes，大整数字节数。 *****************************************************************************/ int large_int_mul_c32( BYTE* psa,BYTE* psb,BYTE* psd,BYTE* pca,int nBytes ) { int i; DWORD dwCarry; DWORD* pwb = (DWORD*)psb; const int npass = nBytes>>2; const int npit = nBytes*2; const int nsize = npit*npass; 8 BYTE* tmp = (BYTE*)xlivAlloc(nsize*2,TRUE,nBytes*2); if( !tmp ) { return LX_FAIL; } BYTE* p = tmp; for( i = 0; i < npass ; i ++ ) { if( LX_OK != large_int_mul_pass_c32(psa,*pwb++,p,&dwCarry,nBytes) ) { goto fail; } p += npit; } p = tmp; for( i = 0; i < npass; i ++ ) { memcpy(p+nsize+i*4,p,npit-i*4); p += npit; } p = tmp+nsize; for( i = 0; i < npass - 1; i ++ ) { large_int_add_c32(p,p+npit,p+npit,&dwCarry,npit); p += npit; } memcpy(psd,p,nBytes); memcpy(pca,p+nBytes,nBytes); if( tmp ) { xlivFree(tmp); } return LX_OK; fail: if( tmp ) { xlivFree(tmp); } return LX_FAIL; } 9 四 调试分析 序号 时间 问题与解决

方法

快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载

1 3月15日 复习数据结构和C++教科

书

关于书的成语关于读书的排比句社区图书漂流公约怎么写关于读书的小报汉书pdf

2 3月19日 上网找相关资料，用数组存放大整数 3 3月24日 开始尝试编写程序 4 3月 27日 大概编写顺序栈 class orderstack 5 3月31日 编写大整数的加法运算函数 6 4月4日 编写“类型转换函数”-将字符型转换成整型 7 4月5日 减法是加法的逆运算思路，编写大整数数的减法函数。 8 4月12日 查找资料开始编写乘法函数，并优化 9 4月15日 解决异号运算时出现的错误 10 4月17日 搜寻资料 11 4月19日 编写主函数，输入函数，把各个函数之间联系起来 12 4月19日 完善程序 13 4月19日 反复调试程序，测试数据，不断改进程序。 14 4月20日 撰写数据结构大整数设计报告。 五 、用户使用说明 配程序界面图解释: 运行程序你会看到如下的界面: 此时选择需要的运算功能，例如键入“1”，在敲击“Enter”，则界面变成 10 此时可输入a的值，如1234567890123456789012345，再敲击“Enter”，程序出现，此时可输入b的值，如9876543210987654321098765，并敲击“Enter”，则界面变成 此时可选择继续运算或退出程序。 六、测试结果 (一)长整数运算: a:1234567890123456789012345 b:9876543210987654321098765 加法结果:11111111101111111110111110 11 运算时间:3.553821ms 减法结果:--8641975320864197532086420 运算时间:3.521396ms 乘法结果: 12193263113702179522618496034720321071359549253925 运算时间:9.687679ms (二)普通短整数运算: 数A:123 数B:987 加法结果:1110 运行时间:0.550890ms 减法结果:-864 运行时间:0.852275ms 乘法结果:121401 运行时间:0.614036ms 注:以上结果测试环境:操作系统 Win7旗舰版、CPU ADMX3、主板 磐正AK785+DDR3、内存 金士顿2GDDR1333、硬盘 西数500G、显卡 铭鑫9800G7N 八、心得小记 这一次的数据结构课程设计，我付出了艰辛的努力，因为一直就觉得自己不擅长做编程一类的工作，这一次更坚定了我的想法。我曾经尝试想把除法运算也完成，但无奈才疏学浅，多番努力之下还是没有实现。不过能做到现在这样，我自己也算是比较满意的了。总的来说，这是一次不错的经历，让我再一次亲近了代码，并深知程序开发的艰辛，不由得对那些奋斗在软件开发行业的人们肃然起敬。 七、附录 源程序代码(不打印) #include #include using namespace std; #include"stdio.h" ////////////////////////////////////////////////////////////和计时器相关的代码块 _LARGE_INTEGER TimeStart; _LARGE_INTEGER TimeEnd; void StartCount() { QueryPerformanceCounter(&TimeStart); }//计时开始 void EndCount() 12 { QueryPerformanceCounter(&TimeEnd); }//计时结束 double Time() { double Freq;//计时器频率 LARGE_INTEGER d; if (QueryPerformanceFrequency(&d)) Freq=d.QuadPart; return (TimeEnd.QuadPart-TimeStart.QuadPart)*1000/Freq; }//返回时差 //////////////////////////////////////////////////////////// #define N 25 /*通过修改N可改变运算位数，4N*/ #define MAX N*4 void init(int a[],int b[],int *p1,int *p2) //数据初始化 { int i,j; char r,s; for(i=0;i0&&j>0;i--,j--,k++) //把每一位对应的数相加，加起来超过9则进 位 { d[k]=a[i]+b[j]+d[k]; if(d[k]>9) {d[k+1]++;d[k]=d[k]-10;} } while(i>0) //把较多位数剩下的值赋给输出变量 { d[k]=d[k]+a[i]; if(d[k]>9) {d[k+1]++;d[k]=d[k]-10;} k++;i--; } while(j>0) { 14 d[k]=d[k]+b[j]; if(d[k]>9) {d[k+1]++;d[k]=d[k]-10;} k++;j--; } d[0]=a[0]+b[0];c[0]=d[0]; if(d[k]==0) k--; for(i=1;k>0;i++,k--)c[i]=d[k]; return(i); } void change(int a[],int b[],int m,int n) //当两异号数相加时，改变其符号以符合加法运算 { int i,j; int c[MAX]; if(m<=n&&b[0]==45) { for(i=1;i=n&&a[0]==45) { a[0]=0; b[0]=45; return; } } int minus(int a[],int b[],int d[],int m,int n) //两个正整数相减 { int c[MAX]={0},i,j,k; for(i=0;i0&&j>0;i--,j--,k++) //把每一位对应的数相减 { if(c[k]<0||a[i]0) //把相减剩下的值赋给输出变量 { c[k]=c[k]+a[i]; if(c[k]<0) {c[k]+=10;c[k+1]--;} k++;i--; } c[k]=a[i]+c[k]; //计算最高位的借位值 while(c[k]<=0&&k>0) k--; for(i=1;k>0;i++) d[i]=c[k--]; return(i); } void minusfun(int a[],int b[],int d[],int m,int n) //两异号数相加选择函数 { int i,j,f=0,g=0; if(a[1]==0) { if(b[0]!=0) printf("-"); for(i=1;ib[i]&&a[0]==45)) g=1; if(a[i]!=b[i]) f=1;} if(f==0) {printf("0\n");return;} if(g==1) { change(a,b,m,n); //printf("结果是a-b="); printf("-"); j=minus(a,b,d,n,m); for(i=1;in&&b[0]==45) { j=minus(a,b,d,m,n); //printf("结果是a-b="); for(i=1;in&&a[0]==45) { change(a,b,m,n); //printf("结果是a-b="); printf("-"); j=minus(a,b,d,m,n); for(i=1;i 0; --i, ++k) ta[k] = a[i]; for(i = n-1, k = 0; i > 0; --i, ++k) tb[k] = b[i]; for(i = 0; i < MAX; ++i) tc[i] = 0; for(i = 0; i < m-1; ++i) for(k = 0; k < n-1; ++k) { tc[i+k+1] += (tc[i+k]+ta[i]*tb[k]) / 10; tc[i+k] = (tc[i+k]+ta[i]*tb[k]) % 10; } for(i = MAX-1; i > 0 && tc[i] == 0; --i); int j = i+2; for(k = 1; i >= 0; --i, ++k) c[k] = tc[i]; return j; } void menu() { printf("=======================================================\n"); printf("1.加法\n"); printf("2.减法\n"); printf("3.乘法\n"); printf("0.退出\n"); printf("=======================================================\n"); printf("请从0~3中选择运算:"); return; } void main() { int a[MAX]={0},b[MAX]={0},c[MAX]={0},d[MAX]={0}; char s; int m,n,i,j; int *p1,*p2; p1=&m;p2=&n; menu(); s=getchar(); 18 getchar(); while(1) { switch(s) { case '0':return; case '1': printf("格式为:a+b\n"); init(a,b,p1,p2); StartCount(); if(a[1]==0&&b[1]==0) {printf("结果是:a+b=0\n"); break;} if(a[0]==b[0]) { j=plus(a,b,c,m,n); printf("结果是:a+b="); if(c[0]!=0) printf("-"); for(i=1;i