大整数运算Word文件下载.docx
《大整数运算Word文件下载.docx》由会员分享，可在线阅读，更多相关《大整数运算Word文件下载.docx（30页珍藏版）》请在冰点文库上搜索。
6.intmenu（）/////菜单函数/////
7.intcompare（orderstackinteger1,orderstackinteger2）/////比较大小函数/////按位比较/////
8.intconvert（charx）/////类型转换函数-将字符型转换成整型/////
2.用户界面流程
Y
N
三、详细设计
1、大整数的表示
在32位字长的系统里，基本数据类型有：
8位数，BYTE，单字节：
char，unsignedchar。
16位数，WORD，字：
short，unsignedshort。
32位数，DWORD，双字：
int，unsignedint。
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位等整数，我们称之为规范整数。
进行大整数的四则运算的时候，一个基本的原理就是把大整数运算降解为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,intnBytes）
返回值：
LX_OK
输入参数：
psa,存放第一个操作数的地址。
psb，第二个操作数的地址。
输出参数：
psd，存放运算结果的地址。
pca，存放进位数据的32位无符号整数地址。
nBytes，大整数字节数。
******************************************************************************/
{
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，然后做加法实现的。
在使用中应当避免小减大的情况。
如果出现了这种情况，判断结果的最高位，如果是1，
结果清零，或者当作负数继续使用。
voidlarge_int_not（BYTE*psa,intnBytes）
大整数取反运算。
for（inti=0;
nBytes;
DWORD*ps=（DWORD*）（psa+i）;
*ps=~*ps;
intlarge_int_reverse（BYTE*psa,intnBytes）
大整数取反并加1。
相当于改变符号。
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））{
if（tmp）{
xlivFree（tmp）;
4、大整数乘法
减半降解法。
设A，B是2n位的整数，A1,A0,B1,B0分别是A，B的高低n位。
A=A1<
<
n+A0;
B=B1<
n+B0;
A和B的乘积可以表示为：
A*B=A0*B0+A1*B0<
n+A0*B1<
n+A1*B1<
2n;
这样我们就把2n位的运算降解为多个n位的乘法运算。
我们首先实现一个递归调用的函数，在降解到32位的时候不再降解直接返回结果。
intlarge_int_mul_half_i（BYTE*psa,BYTE*psb,BYTE*psd,intnBytes）
psd=psa*psb;
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）;
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_add_c32（psd1,psd0,psd1,&
large_int_add_c32（psd1,psdd,psd,&
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;
然后我们用一个看来很简单的实现来调用上面的递归函数。
intlarge_int_mul_half（BYTE*psa,BYTE*psb,BYTE*psd,BYTE*pca,intnBytes）
BYTE*tmp=（BYTE*）xlivAlloc（nBytes*2,TRUE）;
nRe=large_int_mul_half_i（psa,psb,tmp,nBytes）;
if（LX_OK==nRe）{
memcpy（psd,tmp,nBytes）;
memcpy（pca,tmp+nBytes,nBytes）;
减半降解法的思路看来很清晰明了，结果也是正确的。
但是很不幸，同后面我们使用的逐次降解法相比，计算速度低了一个数量级以上：
//减半降解benchmark:
83
//逐次降解benchmark:
5072
大整数乘大整数
intlarge_int_mul_c32（BYTE*psa,BYTE*psb,BYTE*psd,BYTE*pca,intnBytes）
psb，存放第二个操作数的地址。
pca，存放高nBytes字节的内存地址。
constintnpass=nBytes>
2;
constintnpit=nBytes*2;
constintnsize=npit*npass;
BYTE*tmp=（BYTE*）xlivAlloc（nsize*2,TRUE,nBytes*2）;
BYTE*p=tmp;
npass;
i++）{
if（LX_OK!
=large_int_mul_pass_c32（psa,*pwb++,p,&
dwCarry,nBytes））{
gotofail;
}
p+=npit;
p=tmp;
npass;
memcpy（p+nsize+i*4,p,npit-i*4）;
p=tmp+nsize;
npass-1;
large_int_add_c32（p,p+npit,p+npit,&
dwCarry,npit）;
memcpy（psd,p,nBytes）;
memcpy（pca,p+nBytes,nBytes）;
returnLX_FAIL;
四调试分析
序号
时间
问题与解决方法
1
3月15日
复习数据结构和C++教科书
2
3月19日
上网找相关资料，用数组存放大整数
3
3月24日
开始尝试编写程序
4
3月27日
大概编写顺序栈classorderstack
5
3月31日
编写大整数的加法运算函数
6
4月4日
编写“类型转换函数”-将字符型转换成整型
7
4月5日
减法是加法的逆运算思路，编写大整数数的减法函数。
8
4月12日
查找资料开始编写乘法函数，并优化
9
4月15日
解决异号运算时出现的错误
10
4月17日
搜寻资料
11
4月19日
编写主函数，输入函数，把各个函数之间联系起来
12
完善程序
13
反复调试程序，测试数据，不断改进程序。
14
4月20日
撰写数据结构大整数设计报告。
五、用户使用说明
配程序界面图解释:
运行程序你会看到如下的界面：
此时选择需要的运算功能，例如键入“1”，在敲击“Enter”，则界面变成
此时可输入a的值，如1234567890123456789012345，再敲击“Enter”，程序出现
，此时可输入b的值，如9876543210987654321098765，并敲击“Enter”，则界面变成
此时可选择继续运算或退出程序。
六、测试结果
（一）长整数运算：
a：
1234567890123456789012345b：
9876543210987654321098765
加法结果：
111111*********11110111110
运算时间：
3.553821ms
减法结果：
--8641975320864197532086420
3.521396ms
乘法结果：
12193263113702179522618496034720321071359549253925
9.687679ms
（二）普通短整数运算：
数A：
123数B：
987
1110运行时间：
0.550890ms
-864运行时间：
0.852275ms
121401运行时间：
0.614036ms
注：
以上结果测试环境：
操作系统Win7旗舰版、CPUADMX3、主板磐正AK785+DDR3、内存金士顿2GDDR1333、硬盘西数500G、显卡铭鑫9800G7N
八、心得小记
这一次的数据结构课程设计，我付出了艰辛的努力，因为一直就觉得自己不擅长做编程一类的工作，这一次更坚定了我的想法。
我曾经尝试想把除法运算也完成，但无奈才疏学浅，多番努力之下还是没有实现。
不过能做到现在这样，我自己也算是比较满意的了。
总的来说，这是一次不错的经历，让我再一次亲近了代码，并深知程序开发的艰辛，不由得对那些奋斗在软件开发行业的人们肃然起敬。
七、附录
源程序代码（不打印）
#include<
Windows.h>
iostream>
usingnamespacestd;
#include"
stdio.h"
////////////////////////////////////////////////////////////和计时器相关的代码块
_LARGE_INTEGERTimeStart;
_LARGE_INTEGERTimeEnd;
voidStartCount（）
QueryPerformanceCounter（&
TimeStart）;
}//计时开始
voidEndCount（）
TimeEnd）;
}//计时结束
doubleTime（）
doubleFreq;
//计时器频率
LARGE_INTEGERd;
if（QueryPerformanceFrequency（&
d））
Freq=d.QuadPart;
return（TimeEnd.QuadPart-TimeStart.QuadPart）*1000/Freq;
}//返回时差
////////////////////////////////////////////////////////////
#defineN25/*通过修改N可改变运算位数，4N*/
#defineMAXN*4
voidinit（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'
;
a[i]=r-48;
else
a[1]=r-48;
for（i=2;
*p1=i;
输入b的值\n"
s=getchar（）;
if（s==45）
b[0]=s;
for（j=1;
（s=getchar（））!
j++）
b[j]=s-48;
b[1]=s-48;
for（j=2;
b[
升级会员 