大整数运算
初一下册期末试卷-大学校园活动
数据结构课程设计报告
大整数运算的实现
计算机科学学院计算机1班
12XXXXXXX19
XX
2013-12-25
1
一、需求分析
1、课程要求
A．实现大整数的基本运算
B．提供友好的用户界面
C．对于异常的表达式能给出出错提示
2、设计目标
A．软件名称:大整数运算器
B．软件组成：大整数源码.cpp
C．制作平台及相关调试工具：Microsoft Visual C++6.0
D．运行环境：doswin98winMewin2KwinxpWin7
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字节，0x060708090A0B0C0D0E0F
的内存映像是：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=2
24，
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；
rt = (__int64)dwA +
dwB + dwC; 带进位加；
*pwd++ = (DWORD)( t);
低32位输出；
dwC = (DWORD)(rt); 高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<
A1 A0
* B1 B0
A0*B0
A1*B0
A0*B1
A1*B1
A*B = A0*B0 + A1*B0 << n +
A0*B1<
这样我们就把2n位的运算降解为多个n位的乘法运算。
我们首先实现一个递归调用的函数，在降解到32位的时候不再降解直接返回结果。
int large_int_mul_half_i( BYTE* psa,BYTE*
psb,BYTE* psd, int nBytes )
psd = psa * psb;
int large_int_mul_half_i( BYTE* psa,BYTE*
psb,BYTE* psd, int nBytes )
{
if( 4 ==
nBytes ) {
*(QWORD*)psd =
(QWORD)*(DWORD*)psa * *(DWORD*)psb;
return
LX_OK;
}
DWORD dwCarry = 0;
LX_RESULT nRe = LX_OK;
6
const int nDoubleSize = nBytes*2;
const int nHalfSize = 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;
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,nD
oubleSize);
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,nD
oubleSize);
large_int_add_c32(psd1,psd0,psd1,
&dwCarry,nDoubleSize); dwCarry must be zero;
large_int_shift_c32(psd1,-nHalfSize*8,psd1,nD
oubleSize);
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,*p
wb++,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
四
调试分析
序号
1
2
3
4
5
6
7
8
9
10
11
12
13
14
时间
3月15日
3月19日
3月24日
3月
27日
3月31日
4月4日
4月5日
4月12日
4月15日
4月17日
4月19日
4月19日
4月19日
4月20日
问题与解决方法
复习数据结构和C++教科书
上网找相关资料，用数组存放大整数
开始尝试编写程序
大概编写顺序栈
class orderstack
编写大整数的加法运算函数
编写“类型转换函数”-将字符型转换成整型
减法是加法的逆运算思路，编写大整数数的减法函数。
查找资料开始编写乘法函数，并优化
解决异号运算时出现的错误
搜寻资料
编写主函数，输入函数，把各个函数之间联系起来
完善程序
反复调试程序，测试数据，不断改进程序。
撰写数据结构大整数设计报告。
五 、用户使用说明
配程序界面图解释:
运行程序你会看到如下的界面：
此时选择需要的运算功能，例如键入“1”，在敲击“Enter”，则界面变成
10
此时可输入a的值，如45，再敲击“Enter
”，程序出现
此时可输入b的值，如9876543218765，并敲击“Enter”，则界面变成
，
此时可选择继续运算或退出程序。
六、测试结果
（一）长整数运算：
a：45 b：9876543218765
加法结果：110
11
运算时间：3.553821ms
减法结果：--8641975326420
运算时间：3.521396ms
乘法结果： 796359549253925
运算时间：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
和计时器相关的代码块
_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=rt;
return (rt)*1000Freq;
}返回时差
#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;i
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
13
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;
}
int plus(int
a[],int b[],int c[],int m,int n) 两个正整数相加
{
int d[MAX]={0},i,j,k;
for(i=0;i
{
for(i=0;i
}
if(b[1]==0)
{
for(i=0;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)
{
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
}
if(m>=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;i
{
if(c[k]<0||a[i]
c[k]=c[k]+a[i]-b[j];
if(c[k]<0)
{
c[k]+=10;
c[k+1]--;
}
15
}
else
c[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);
}
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;i
}
if(b[1]==0)
{
if(a[0]!=0) printf(
for(i=1;i
}
if(m==n)
{
for(i=1;i
if(a[i]!=b[i]) f=1;}
if(f==0)
{printf(
if(g==1)
{
change(a,b,m,n); printf(结果是a-b=
printf(
for(i=1;i
}
16
else
if(a[0]==45&&b[0]==0)
{
j=minus(b,a,d,n,m); printf(结果是a-b=
for(i=1;i
}
else
{
j=minus(a,b,d,m,n);
printf(结果是a-b=
for(i=1;i
}
}
if(m>n&&b[0]==45)
{
j=minus(a,b,d,m,n); printf(结果是a-b=
for(i=1;i
}
if(m
change(a,b,m,n);
printf(结果是a-b=
printf(
for(i=1;i
}
if(m>n&&a[0]==45)
{
change(a,b,m,n);
printf(结果是a-b=
printf(
for(i=1;i
}
if(m
j=minus(b,a,d,n,m); printf(结果是a-b=
for(i=1;i
}
}
int multi(int a[],int b[],int c[],int
m,int n) 两个正整数相乘
{
int ta[MAX], tb[MAX],
tc[MAX];
17
int i,
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);
int j = i+2;
for(k = 1; i >= 0;
--i, ++k)
c[k] = tc[i];
return j;
}
void menu()
{
printf(
printf(加法n
printf(减法n
printf(乘法n
printf(退出n
printf(
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+bn
init(a,b,p1,p2);
StartCount();
if(a[1]==0&&b[1]==0) {printf(结果是:a+b=0n
if(a[0]==b[0])
{
j=plus(a,b,c,m,n);
printf(结果是:a+b=
if(c[0]!=0)
printf(
for(i=1;i
else {printf(结果是:a+b=
printf(
case '2':
printf(格式为:a-bn
init(a,b,p1,p2);
StartCount();
if(b[0]==0) b[0]=45;
else if(b[0]==45) b[0]=0;
if(a[1]==0&&b[1]==0) {printf(结果是:a-b=0n
if(a[0]==b[0])
{
j=plus(a,b,c,m,n);
printf(结果是:a-b=
if(c[0]!=0)
printf(
for(i=1;i
else {printf(结果是:a-b=
printf(
case '3':
init(a,b,p1,p2);
StartCount();
if(a[1]==0||b[1]==0) {printf(结果是:0n
j =
multi(a,b,c,m,n);
printf(结果是:
if((a[0]==45&&b[0]==0)||(b[0]==45&&a[0]==0))
printf(
for(i=1;i
}
19
}
}
EndCount();
printf(计算时间为：%lf msnnn
menu();
s=getchar();
getchar();
20