大整數運算的實現(xiàn)

PAGEPAGE20數據結構課程設計報告大整數運算的實現(xiàn)計算機科學學院計算機5班一、需求分析1、課程要求A．實現(xiàn)大整數的基本運算B．提供友好的用戶界面C．對于異常的表達式能給出出錯提示2、設計目標A．軟件名稱:大整數運算器B．軟件組成：大整數源碼.cppC．制作平臺及相關調試工具：MicrosoftVisualC++6.0D．運行環(huán)境：dos/win98/winMe/win2K/winxp/Win7E．性能特點：1.當用戶輸入一個合法的算術表達式后，能夠返回正確的結果2.能夠進行加、減、乘三種運算3.對于異常表達式能夠出錯誤提示4.能顯示運算時間二、設計概要1.相關函數介紹voidmain()/////主函數/////voidadd(orderstack&integer1,orderstack&integer2,orderstack&integer3)/////加法函數/////voidreduce(orderstack&integer1,orderstack&integer2,orderstack&integer3)/////減法函數/////voidmultiply(orderstack&integer1,orderstack&integer2,orderstack&integer3)/////乘法函數/////模擬乘法豎式算法/////voidinput(orderstack&integer1,orderstack&integer2)////輸入函數/////intmenu()/////菜單函數/////intcompare(orderstackinteger1,orderstackinteger2)/////比較大小函數/////按位比較/////intconvert(charx)/////類型轉換函數-將字符型轉換成整型/////2.用戶界面流程選擇需要的運算功能選擇需要的運算功能減法減法加法乘法加法乘法初始化list1list2初始化list1list2初始化list1list2初始化list1list2初始化list1list2初始化list1list2輸入數據至list1list2輸入數據至list1list2輸入數據至list1list2輸入數據至list1list2輸入數據至list1list2輸入數據至list1list2乘法運算減法運算加法運算乘法運算減法運算加法運算輸出結果輸出結果輸出結果輸出結果輸出結果輸出結果判斷是否要再次運算 判斷是否要再次運算YN退出結束退出結束三、詳細設計1、大整數的表示 在32位字長的系統(tǒng)里，基本數據類型有： 8位數，BYTE，單字節(jié)：char，unsignedchar。 16位數，WORD，字：short，unsignedshort。 32位數，DWORD，雙字：int，unsignedint。 64位數，QWORD，四字：__int64,unsigned__int64 這些基本數據類型的運算可以被機器指令所直接支持。 在x86平臺上，多個字節(jié)的數據存放順序是，低位數據存放在低位地址。 比如，0x00010203,在內存中的存放順序是03，02，01，00。照此類推，128位整數，8字，16字節(jié)，0x000102030405060708090A0B0C0D0E0F的內存映像是：0F，0E，0D，0C，0B，0A，09，08，07，06，05，04，03，02，01，00。位數是2的整數次方，64位，128位，256位等整數，我們稱之為規(guī)范整數。進行大整數的四則運算的時候，一個基本的原理就是把大整數運算降解為32位四則運算的復合運算。降解的方式可以是位數減半，即256位降解為128位，128位降解為64位，直到降解為機器指令支持范圍內的整數。這樣的降解過程用到的所有的中間變量都是規(guī)范的整數。也可以是從高到低，每次降解32位。這樣的話在降解過程中我們會使用到256-32=224，224-32=192，192-32=160等長度不等于2的整數次方的整數，我們稱之為不規(guī)范的整數。減半降解運算過程比較容易理解，而逐次降解則會獲得較好的性能。大整數的符號。一般來說，大整數運算中，負數的使用是非常少的。如果要使用符號的話，同基本數據一樣，最高位表示符號，剩余的數位用來表示有效值。2、大整數加法 1.2.0在大整數四則運算中，加法是基本的運算，也最容易實現(xiàn)。LX_RESULTlarge_int_add_c32(BYTE*psa,BYTE*psb,BYTE*psd,DWORD*pca,intnBytes)返回值：LX_OK輸入參數：psa,存放第一個操作數的地址。輸入參數：psb，第二個操作數的地址。輸出參數：psd，存放運算結果的地址。輸出參數：pca，存放進位數據的32位無符號整數地址。輸入參數：nBytes，大整數字節(jié)數。******************************************************************************/LX_RESULTlarge_int_add_c32(BYTE*psa,BYTE*psb,BYTE*psd,DWORD*pca,intnBytes){ inti; DWORDdwA; DWORDdwB; DWORDdwC=0; DWORD*pwa=(DWORD*)psa; DWORD*pwb=(DWORD*)psb; DWORD*pwd=(DWORD*)psd; for(i=0;i<nBytes;i+=4){ ULARGE_INTEGERuld; dwA=*pwa++;//取第一個操作數DWORD； dwB=*pwb++;//取第二個操作數DWORD； uld.QuadPart=(__int64)dwA+dwB+dwC;//帶進位加； *pwd++=(DWORD)(uld.LowPart);//低32位輸出； dwC=(DWORD)(uld.HighPart);//高32位為進位； } *pca=dwC;//輸出進位； returnLX_OK;}3、大整數減法減法在大整數運算里面需要加以注意。減法是通過把操作數取反并加1，然后做加法實現(xiàn)的。在使用中應當避免小減大的情況。如果出現(xiàn)了這種情況，判斷結果的最高位，如果是1，結果清零，或者當作負數繼續(xù)使用。voidlarge_int_not(BYTE*psa,intnBytes)大整數取反運算。voidlarge_int_not(BYTE*psa,intnBytes){ for(inti=0;i<nBytes;i+=4){ DWORD*ps=(DWORD*)(psa+i); *ps=~*ps; }}intlarge_int_reverse(BYTE*psa,intnBytes)大整數取反并加1。相當于改變符號。intlarge_int_reverse(BYTE*psa,intnBytes){ DWORDdwCarry; large_int_not(psa,nBytes); returnlarge_int_add_pass_c32(psa,1,psa,&dwCarry,nBytes);}//LX_RESULTlarge_int_sub_c32(//BYTE*psa,BYTE*psb,BYTE*psd,DWORD*pca,intnBytes)*****************************************************************************/LX_RESULTlarge_int_sub_c32(BYTE*psa,BYTE*psb,BYTE*psd,DWORD*pca,intnBytes){ BYTE*tmp=(BYTE*)xlivAlloc(nBytes,TRUE); if(!tmp){ returnLX_FAIL; } memcpy(tmp,psb,nBytes); large_int_reverse(tmp,nBytes); if(LX_OK!=large_int_add_c32(psa,tmp,psd,pca,nBytes)){ returnLX_FAIL; } if(tmp){ xlivFree(tmp); } returnLX_OK;}4、大整數乘法減半降解法。設A，B是2n位的整數，A1,A0,B1,B0分別是A，B的高低n位。A=A1<<n+A0;B=B1<<n+B0;A和B的乘積可以表示為：AA1A0*B1B0A0*B0A1*B0A0*B1A1*B1A*B=A0*B0+A1*B0<<n+A0*B1<<n+A1*B1<<2n;這樣我們就把2n位的運算降解為多個n位的乘法運算。我們首先實現(xiàn)一個遞歸調用的函數，在降解到32位的時候不再降解直接返回結果。intlarge_int_mul_half_i(BYTE*psa,BYTE*psb,BYTE*psd,intnBytes)psd=psa*psb;intlarge_int_mul_half_i(BYTE*psa,BYTE*psb,BYTE*psd,intnBytes){ if(4==nBytes){ *(QWORD*)psd=(QWORD)*(DWORD*)psa**(DWORD*)psb; returnLX_OK; } DWORDdwCarry=0; LX_RESULTnRe=LX_OK; constintnDoubleSize=nBytes*2; constintnHalfSize=nBytes>>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; gotofail; } 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);//dwCarrymustbezero; 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);//dwCarrymustbezero; 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); } returnnRe;}然后我們用一個看來很簡單的實現(xiàn)來調用上面的遞歸函數。intlarge_int_mul_half(BYTE*psa,BYTE*psb,BYTE*psd,BYTE*pca,intnBytes){ LX_RESULTnRe=LX_OK; BYTE*tmp=(BYTE*)xlivAlloc(nBytes*2,TRUE); if(!tmp){ nRe=LX_FAIL; gotofail; }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); } returnnRe;}減半降解法的思路看來很清晰明了，結果也是正確的。但是很不幸，同后面我們使用的逐次降解法相比，計算速度低了一個數量級以上：//減半降解benchmark:83//逐次降解benchmark:5072大整數乘大整數intlarge_int_mul_c32(BYTE*psa,BYTE*psb,BYTE*psd,BYTE*pca,intnBytes)返回值：LX_OK輸入參數：psa,存放第一個操作數的地址。輸入參數：psb，存放第二個操作數的地址。輸出參數：psd，存放運算結果的地址。輸出參數：pca，存放高nBytes字節(jié)的內存地址。輸入參數：nBytes，大整數字節(jié)數。*****************************************************************************/intlarge_int_mul_c32(BYTE*psa,BYTE*psb,BYTE*psd,BYTE*pca,intnBytes){ inti; DWORDdwCarry; DWORD*pwb=(DWORD*)psb; constintnpass=nBytes>>2; constintnpit=nBytes*2; constintnsize=npit*npass; BYTE*tmp=(BYTE*)xlivAlloc(nsize*2,TRUE,nBytes*2); if(!tmp){ returnLX_FAIL; } BYTE*p=tmp; for(i=0;i<npass;i++){ if(LX_OK!=large_int_mul_pass_c32(psa,*pwb++,p,&dwCarry,nBytes)){ gotofail; } 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); } returnLX_OK;fail: if(tmp){ xlivFree(tmp); } returnLX_FAIL;} 四調試分析序號時間問題與解決方法13月15日復習數據結構和C++教科書23月19日上網找相關資料，用數組存放大整數33月24日開始嘗試編寫程序43月27日大概編寫順序棧classorderstack53月31日編寫大整數的加法運算函數64月編寫“類型轉換函數”-將字符型轉換成整型74月減法是加法的逆運算思路，編寫大整數數的減法函數。84月查找資料開始編寫乘法函數，并優(yōu)化94月解決異號運算時出現(xiàn)的錯誤104月搜尋資料114月編寫主函數，輸入函數，把各個函數之間聯(lián)系起來124月完善程序134月反復調試程序，測試數據，不斷改進程序。144月撰寫數據結構大整數設計報告。五、用戶使用說明配程序界面圖解釋:運行程序你會看到如下的界面：此時選擇需要的運算功能，例如鍵入“1”，在敲擊“Enter”，則界面變成此時可輸入a的值，如1234567890123456789012345，再敲擊“Enter”，程序出現(xiàn)，此時可輸入b的值，如9876543210987654321098765，并敲擊“Enter”，則界面變成此時可選擇繼續(xù)運算或退出程序。六、測試結果（一）長整數運算：a：1234567890123456789012345b：9876543210987654321098765加法結果：11111111101111111110111110運算時間：3.553821ms減法結果：--8641975320864197532086420運算時間：3.521396ms乘法結果：12193263113702179522618496034720321071359549253925運算時間：9.687679ms（二）普通短整數運算：數A：123數B：987加法結果：1110運行時間：0.550890ms減法結果：-864運行時間：0.852275ms乘法結果：121401運行時間：0.614036ms注：以上結果測試環(huán)境：操作系統(tǒng)Win7旗艦版、CPUADMX3、主板磐正AK785+DDR3、內存金士頓2GDDR1333、硬盤西數500G、顯卡銘鑫9800G7N八、心得小記這一次的數據結構課程設計，我付出了艱辛的努力，因為一直就覺得自己不擅長做編程一類的工作，這一次更堅定了我的想法。我曾經嘗試想把除法運算也完成，但無奈才疏學淺，多番努力之下還是沒有實現(xiàn)。不過能做到現(xiàn)在這樣，我自己也算是比較滿意的了?？偟膩碚f，這是一次不錯的經歷，讓我再一次親近了代碼，并深知程序開發(fā)的艱辛，不由得對那些奮斗在軟件開發(fā)行業(yè)的人們肅然起敬。七、附錄源程序代碼（不打?。?include<Windows.h>#include<iostream>usingnamespacestd;#include"stdio.h"http:////////////////////////////////////////////////////////////和計時器相關的代碼塊_LARGE_INTEGERTimeStart;_LARGE_INTEGERTimeEnd;voidStartCount(){ QueryPerformanceCounter(&TimeStart);}//計時開始voidEndCount(){ QueryPerformanceCounter(&TimeEnd);}//計時結束doubleTime(){ doubleFreq;//計時器頻率 LARGE_INTEGERd; if(QueryPerformanceFrequency(&d)) Freq=d.QuadPart; return(TimeEnd.QuadPart-TimeStart.QuadPart)*1000/Freq;}//返回時差////////////////////////////////////////////////////////////#defineN25/*通過修改N可改變運算位數，4N*/#defineMAXN*4voidinit(inta[],intb[],int*p1,int*p2) //數據初始化{ inti,j; charr,s; for(i=0;i<MAX;i++) {a[i]=0; b[i]=0;} printf("輸入a的值\n"); r=getchar(); if(r==45) { a[0]=r; for(i=1;(r=getchar())!='\n';i++) a[i]=r-48; } else { a[1]=r-48; for(i=2;(r=getchar())!='\n';i++) a[i]=r-48; } *p1=i; printf("輸入b的值\n"); s=getchar(); if(s==45) { b[0]=s; for(j=1;(s=getchar())!='\n';j++) b[j]=s-48; } else { b[1]=s-48; for(j=2;(s=getchar())!='\n';j++) b[j]=s-48; } *p2=j;}intplus(inta[],intb[],intc[],intm,intn) //兩個正整數相加{ intd[MAX]={0},i,j,k; for(i=0;i<MAX;i++)c[i]=0; if(a[1]==0) { for(i=0;i<n;i++)c[i]=b[i]; return(i); } if(b[1]==0) { for(i=0;i<m;i++)c[i]=a[i]; return(i); } for(i=m-1,j=n-1,k=1;i>0&&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) { 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);}voidchange(inta[],intb[],intm,intn) //當兩異號數相加時，改變其符號以符合加法運算{ inti,j; intc[MAX]; if(m<=n&&b[0]==45) { for(i=1;i<m;i++) c[i]=a[i]; for(i=1,j=1;j<n;i++,j++) a[i]=b[j]; for(i=1,j=1;j<n;i++,j++) b[i]=c[j]; for(j=i;j<MAX;j++) b[j]=0; return; } if(m>=n&&a[0]==45) { a[0]=0; b[0]=45; return; }}intminus(inta[],intb[],intd[],intm,intn) //兩個正整數相減{ intc[MAX]={0},i,j,k; for(i=0;i<MAX;i++)d[i]=0; for(i=m-1,j=n-1,k=1;i>0&&j>0;i--,j--,k++) //把每一位對應的數相減 { if(c[k]<0||a[i]<b[j]) { c[k]=c[k]+a[i]-b[j]; if(c[k]<0) { c[k]+=10; c[k+1]--; } } elsec[k]=a[i]-b[j]; } while(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);}voidminusfun(inta[],intb[],intd[],intm,intn) //兩異號數相加選擇函數{ inti,j,f=0,g=0; if(a[1]==0) { if(b[0]!=0)printf("-"); for(i=1;i<n;i++)printf("%d",b[i]); printf("\n");return; } if(b[1]==0) { if(a[0]!=0)printf("-"); for(i=1;i<m;i++)printf("%d",a[i]); printf("\n");return; } if(m==n) { for(i=1;i<m;i++) {if((a[i]<b[i]&&b[0]==45)||(a[i]>b[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;i<j;i++)printf("%d",d[i]); printf("\n");return; } elseif(a[0]==45&&b[0]==0) { j=minus(b,a,d,n,m);//printf("結果是a-b="); for(i=1;i<j;i++)printf("%d",d[i]); printf("\n");return; } else { j=minus(a,b,d,m,n);//printf("結果是a-b="); for(i=1;i<j;i++)printf("%d",d[i]); printf("\n");return; } } if(m>n&&b[0]==45) { j=minus(a,b,d,m,n);//printf("結果是a-b="); for(i=1;i<j;i++)printf("%d",d[i]); printf("\n");return; } if(m<n&&b[0]==45) { change(a,b,m,n);//printf("結果是a-b="); printf("-");j=minus(a,b,d,n,m); for(i=1;i<j;i++)printf("%d",d[i]); printf("\n"); return; } if(m>n&&a[0]==45) { change(a,b,m,n);//printf("結果是a-b="); printf("-");j=minus(a,b,d,m,n); for(i=1;i<j;i++)printf("%d",d[i]); printf("\n"); return; } if(m<n&&a[0]==45) { j=minus(b,a,d,n,m);//printf("結果是a-b="); for(i=1;i<j;i++)printf("%d",d[i]); printf("\n");return; }}intmulti(inta[],intb[],intc[],intm,intn) //兩個正整數相乘{ intta[MAX],tb[MAX],tc[MAX]; inti,k; for(i=m-1,k=0;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); intj=i+2; for(k=1;i>=0;--i,++k) c[k]=tc[i]; returnj;}voidmenu(){ printf("=======================================================\n");