|
研究密码学过程中,遇到数据位比较长,c语言本身具有的数据类型无法满足超长位数的整数进行四则运算,因此特意写了这个程序。
参考了网上部分类似代码,目前网上能找到的类似代码,基本都有部分瑕疵,本文将我发现的瑕疵全部改进。
本文能实现25000位整数的加减乘除运算,经过本人的测试,基本正常。最大位数只验证了4位,25000位未验证。希望有兴趣的黑友,帮忙下载测试,若发现问题,希望能在评论中提出,我将会及时改进,谢谢。
以下代码在vc6.0中编译运行通过,将下列代码全部放于一个.c文件中即可。
关于程序细节方面,见下文的程序注释。
- /**************************************************************
- *功能:实现大整数的加减乘除四则运算,最大位长为MAX-1,1为符号位
- *思路:利用数组实现,尽量将四则运算封装成函数;
- * 1.开始菜单;数组初始化,避免影响第二次运算结果接收数据;提示信息
- * 2.接收数据
- * 3.先判断进行哪种运算(加减乘除退出),再判断输入的两个数据是否为0
- * (加减时,若ab都为0,则直接输出结果0;乘时,则ab任一为0,则直接输出结果0;
- * 除时,b为0,则输出提示“输入错误”,b不为0a为0,则直接输出结果0);
- * 4.再判断a和b的符号
- * 加时:同号相加则调加;+-相加则将-变+再调减;-+相加,将-变+,再调换成+-,再调减
- * 减时:++相减则调减;+-相减则将-变+再调加;-+相减则将+变-再调加;--相减,将-变+再交换ab值,再调减
- * 乘时:异号相乘结果添'-'号,同号相乘不处理;ab符号皆调正,子函数不处理符号位
- * 除时:异号相除结果添'-'号,同号相乘不处理;ab符号皆调正,子函数不处理符号位;若有小数则,则用余数形式显示。
- * 5.调用子函数处理数据
- * 5.输出结果
- *注意!!:数组定义大小要注意,计算结果有的比最大位数大1,有的大2倍+1;
- * 因内存限制了数组下标,MAX最大值为25001,本程序运行正常;超出此值,程序运行将出现问题!!!
- *测试数据:加法:0+0=0;0+5=5;5+0=5;5+5=10;5+(-8)=-3;(-8)+5=-3;(-5)+(-5)=-10
- * 11+12=23;11+123=134;123+11=134; -11+12=1;-11+123=112;-123+11=-112
- * 80848+36678623=36759471;-2998602+(-44953)=-3043555;-8+39639213=39639205
- * 减法:0-0=0;0-5=-5;5-0=5;5-5=0;5-(-8)=13;(-8)-5=-13;(-5)-(-5)=0
- * 11-12=-1;11-123=-112;123-11=112; -11-12=-23;-11-123=-134;-123-11=-134;
- * -5429891960-(5838364)=-5435730324;5039-(-41490954)=41495993
- * 乘法:0*0=0;0*5=0;5*0=0;5*5=25;5*(-8)=-40;(-8)*5=-40;(-5)*(-5)=25
- * 11*12=132;11*123=1353;123*11=1353; -11*12=-132;-11*123=-1353;-123*11=-1353;
- * -49*(-128)=6272 4268*13197386=56326443448
- * 除法:0/0=--;0/5=0;5/0=--;5/5=1;5/(-8)=-0……5;(-8)/5=-1……3;(-5)/(-5)=1
- * 11/12=0……11;11/123=0……11;123/11=11……2; -11/12=-0……11;-11/123=-0……11;-123/11=-11……2;
- * 043714/956540=0(输入数据不规范)默认数据最高位非0
- * 7425776/338=21969……254
- * 8784015415/3545=2477860……1715
- * 将#define MAX 25001 改为 #define MAX 5;再将a=b=9999,分别进行加减乘除,结果分别为19998、0、99980001、1
- * 验证最大位数计算正确与否 再将a=b=-9999,分别进行加减乘除,结果分别为-19998、0、99980001、1
- * 验证结束后,根据实际情况,改其值 再将a=9999,b=-9999,分别进行加减乘除,结果分别为0、19998、-99980001、-1
- * 再将a=-9999,b=9999,分别进行加减乘除,结果分别为0、-19998、-99980001、-1
- **************************************************************/
- #include <stdio.h>
- #define MAX 25001 // 大数的最大位数,包括一位符号位,实际数字位数为MAX-1
- /*****************************************
- *功能说明:打印菜单函数
- * 仅提示用户选择何种运算
- * 不接收不判断数据
- *****************************************/
- void menu() //菜单
- {
- printf("===============大整数(最大数字位数25000位)计算器==================\n");
- printf("1.加法 2.减法 3.乘法 4.除法 0.退出\n");
- printf("请从0~4中选择:");
- }
- /*****************************************
- *功能说明: 读入所要计算的数值,数据初始化
- *参数说明: a[]第一个数值, b[]第二个数值
- * *p1第一个数值长度(包括符号位)
- * *p2第二个数值长度(包括符号位)
- *其他说明: 参数传递都采用传地址的方式,
- * 调用本函数前,需要提前定义好相关变量
- * 数组存储数据为大端方式:
- * 即:数值-12在数组中的下标依次为0,1,2
- * 数组第0位为符号位,0为正,非0为负
- *****************************************/
- void init(int a[], int b[], int *p1, int *p2) // 输入
- {
- int i,j;
- char r,s;
- for(i=0;i<MAX;i++) // 数组清零,以确保第二次之后的运行结果不受影响
- {
- a[i]=0;
- b[i]=0;
- }
- printf("请输入(0123456789+-)中的任意字符\n请输入第一个(a)数值:"); // 默认输入正确,不进行判断
- r=getchar();
- if(r=='-') // "-" 输入负数
- {
- 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)数值:"); // 默认输入正确,不进行判断
- s=getchar();
- if(s=='-')
- {
- 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;
- }
- /*****************************************
- *功能说明: 两个同号整数相加(++、--)
- *参数说明: a[]第一个数值, b[]第二个数值
- * c[]第一二数值相加的结果
- * 返回值i为c[]数组的长度,即结果的实际长度
- * m第一个数值长度(包括符号位)
- * n第二个数值长度(包括符号位)
- *其他说明: 数组参数传递采用传地址的方式,
- * 调用本函数前,需要提前定义好相关变量
- * a[],b[],c[]数组存储数据为大端方式:
- * 即:数值-12在数组中的下标依次为0,1,2
- * d[]数组存储数据为小端方式:
- * 即:数值-12在数组中的下标依次为2,1,0
- *****************************************/
- int plus(int a[], int b[], int c[], int m, int n) //加法运算
- {
- int d[MAX+1]={0},i,j,k; // 和比最大位数可能长1位
- if(a[1]==0) // 处理a+b时,有a为0的情况
- {
- for(i=0;i<n;i++)
- c[i]=b[i];
- return(i);
- }
- if(b[1]==0) // 处理a+b时,有b为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++) // 处理a+b时,有a,b都不为0的情况
- {
- d[k]=a[i]+b[j]+d[k];
- if(d[k]>9) // 处理和进位的情况
- {
- d[k+1]=1;
- d[k]=d[k]-10;
- }
- }
- while(i>0) // 处理a+b时, a长度>b长度的情况
- {
- d[k]=d[k]+a[i];
- if(d[k]>9)
- {
- d[k+1]=1;
- d[k]=d[k]-10;
- }
- k++;
- i--;
- }
- while(j>0) // 处理a+b时, a长度<b长度的情况
- {
- d[k]=d[k]+b[j];
- if(d[k]>9)
- {
- d[k+1]=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);
- }
- /*****************************************
- *功能说明: 两个正整数相减 (++)
- *参数说明: a[]第一个数值, b[]第二个数值
- * c[]第一二数值相减的结果
- * 返回值i为d[]数组的长度,即结果的实际长度
- * m第一个数值长度(包括符号位)
- * n第二个数值长度(包括符号位)
- *其他说明: 数组参数传递采用传地址的方式,
- * 调用本函数前,需要提前定义好相关变量
- * a[],b[],c[]数组存储数据为大端方式:
- * 即:数值-12在数组中的下标依次为0,1,2
- * d[]数组存储数据为小端方式:
- * 即:数值-12在数组中的下标依次为2,1,0
- *****************************************/
- int minus(int a[], int b[], int c[], int m, int n) //减法运算
- {
- int d[MAX+1]={0},i,j,k,T; // 多一位可能存在的借位位
-
- if (m<n) // a<b 位
- {
- a: T=m;
- m=n;
- n=T;
- for(i=m-1,j=n-1,k=1;i>0&&j>0;i--,j--,k++)
- {
- if(d[k]<0||b[i]<a[j]) // 有借位情况
- {
- d[k]=d[k]+b[i]-a[j];
- if(d[k]<0)
- {
- d[k]+=10;
- d[k+1]=-1;
- }
- }
- else // 无借位情况
- d[k]=b[i]-a[j];
- }
- while(i>0)
- {
- d[k]=d[k]+b[i];
- if(d[k]<0)
- {
- d[k]+=10;
- d[k+1]--;
- }
- k++;
- i--;
- }
- d[k]=b[i]+d[k];
- while(d[k]<=0&&k>0)
- k--;
- for(i=1;k>0;i++)
- c[i]=d[k--];
- c[0]=45;
- return(i);
- }
- if(m>n) // a>b 位
- {
- b: for(i=m-1,j=n-1,k=1;i>0&&j>0;i--,j--,k++)
- {
- if(d[k]<0||a[i]<b[j]) // 有借位情况
- {
- d[k]=d[k]+a[i]-b[j];
- if(d[k]<0)
- {
- d[k]+=10;
- d[k+1]=-1;
- }
- }
- else // 无借位情况
- d[k]=a[i]-b[j];
- }
- while(i>0)
- {
- d[k]=d[k]+a[i];
- if(d[k]<0)
- {
- d[k]+=10;
- d[k+1]--;
- }
- k++;
- i--;
- }
- d[k]=a[i]+d[k];
-
- while(d[k]<=0&&k>0)
- k--;
- for(i=1;k>0;i++)
- c[i]=d[k--];
- return(i);
- }
- // a==b 位数
- {
- for(i=1; i<m; i++)
- {
- if(a[i]>b[i]) // a>b 数值
- goto b;
- else if(a[i]<b[i]) // a<b 数值
- goto a;
- }
- c[0]=0; //a=b
- c[1]=0;
- return 2;
- }
- }
- /*****************************************
- *功能说明: 两个整数相乘
- *注:函数运算过程中未处理符号
- *参数说明: a[]第一个数值, b[]第二个数值
- * c[]第一二数值相乘的结果
- * 返回值k为c[]数组的长度,即结果的实际长度(包括符号位)
- * m第一个数值长度(包括符号位)
- * n第二个数值长度(包括符号位)
- *其他说明: 数组参数传递采用传地址的方式,
- * 调用本函数前,需要提前定义好相关变量
- * a[],b[],c[]数组存储数据为大端方式:
- * 即:数值-12在数组中的下标依次为0,1,2
- * d[]数组存储数据为小端方式:
- * 即:数值-12在数组中的下标依次为2,1,0
- *★ Comba 乘法 (Comba Multiplication)原理实现
- * Comba 乘法以(在密码学方面)不太出名的 Paul G. Comba 得名。
- * 和普通的笔算乘法很类似,只是每一次单精度乘法只是单纯计算乘法,不计算进位,进位留到每一列累加后进行。
- * Comba 乘法无需进行嵌套进位来计算乘法,时间复杂度和基线乘法一样
- * Comba 乘法则按列计算,先累加,然后传递进位,减少了计算量,所以速度快。
- ************************************************************/
- int multi(int a[], int b[], int c[], int m, int n) //正整数乘法运算
- {
- int d[2*MAX+1]={0},i,j,k,s;
- for(i=0;i<MAX;i++)
- c[i]=0;
- if(m<=n) // a位数大于等于b位数
- {
- for(i=m-1,s=1;i>0;i--,s++) // 单纯计算乘法,不计算进位
- {
- for(j=n-1,k=1*s;j>0;j--,k++)
- {
- d[k]=a[i]*b[j]+d[k];
- }
- }
- for(i=1;i<k;i++) // 处理进位
- {
- if(d[i]>9)
- {
- d[i+1]=d[i+1]+d[i]/10;
- d[i] = d[i]%10;
- }
- }
- if(d[i]==0) // 数值和最高位没有进位
- i--;
- for(k=1;i>0;k++,i--)
- c[k]=d[i];
- return k;
- }
- else // a位数大于b位数
- {
- for(i=n-1,s=1;i>0;i--,s++) // 单纯计算乘法,不计算进位
- {
- for(j=m-1,k=1*s;j>0;j--,k++)
- {
- d[k]=b[i]*a[j]+d[k];
- }
- }
- // 处理进位
- for(i=1;i<k;i++)
- {
- if(d[i]>9)
- {
- d[i+1]=d[i+1]+d[i]/10;
- d[i] = d[i]%10;
- }
- }
- if(d[i]==0) // 数值和最高位没有进位
- i--;
- for(k=1;i>0;k++,i--)
- c[k]=d[i];
- return k;
- }
- }
- /*****************************************
- *功能说明: 用长度为len1的大整数p1减去长度为len2的大整数p2
- * 结果存在p1中,返回值代表结果的长度
- * 不够减:返回-1 , 正好够:返回0
- *数组数值为:p1,p2小端
- *其他说明: 数组参数传递采用传地址的方式,
- * 调用本函数前,需要提前定义好相关变量
- * 本函数的作用仅与Division函数结合实现除法
- *****************************************/
- int SubStract(int *p1, int len1, int *p2, int len2)
- {
- int i;
- if(len1 < len2)
- return -1;
- if(len1 == len2 )
- { // 判断p1 > p2
- for(i = len1-1; i >= 0; i--)
- {
- if(p1[i] > p2[i]) // 若大,则满足条件,可做减法
- break;
- else if(p1[i] < p2[i]) // 否则返回-1
- return -1;
- }
- }
- for(i = 0; i <= len1-1; i++) // 从低位开始做减法
- {
- p1[i] -= p2[i]; // 相减
- if(p1[i] < 0) // 若是否需要借位
- { // 借位
- p1[i] += 10;
- p1[i+1]--;
- }
- }
- for(i = len1-1; i >= 0; i--) // 查找结果的最高位
- {
- if( p1[i] ) //最高位第一个不为0
- return (i+1); //得到位数并返回
- }
- return 0; //两数相等的时候返回0
- }
- /*****************************************
- *功能说明: 大数除法---结果不包括小数点
- **注:函数运算过程中未处理符号
- *参数说明: a[]被除数 b[]除数
- * c[]第一二数值相除的结果即:a/b=c
- * 返回值len为c[]数组的长度,即结果的实际长度
- * m第一个数值长度(包括符号位)
- * n第二个数值长度(包括符号位)
- * *p表示余数的位数,位数大于0时,表示有余数;否则无余数
- * num_a[]保存最后余数的
- *其他说明: 数组参数传递采用传地址的方式,
- * 调用本函数前,需要提前定义好相关变量
- * a[],b[],c[],num_a[]数组存储数据为大端方式:
- * 即:数值-12在数组中的下标依次为0,1,2
- *****************************************/
- int Division(int a[], int b[], int c[] , int m, int n, int *p, int num_a[])
- {
- int i, j;
- int len=0;
- int nTimes; //两大数相差位数
- int nTemp; //Subtract函数返回值
- int num_b[MAX] = {0}; //除数
- int num_c[MAX+1] = {0}; //商
- if( m < n ) //如果被除数小于除数,直接返回-1,表示结果为0……a
- {
- return -1;
- }
- if(m==n)
- {
- for(i=1; i<m; i++)
- {
- if(a[i]>b[i]) // 够减一次否
- break;
- }
- if(i==m && a[m-1]<b[m-1]) // 包含符号位
- return -1; // 如果被除数小于除数,直接返回-1,表示结果为0……a
-
- }
- nTimes = m - n; //相差位数
- //翻转保存的数据
- for( j = 1, i = m-1; i >= 0; j++, i-- )
- num_a[j] = a[i];
- for( j = 1, i = n-1; i >= 0; j++, i-- )
- num_b[j] = b[i];
-
- for ( i=m-1; i>=0; i-- ) //将除数扩大,使得除数和被除数位数相等
- {
- if ( i>=nTimes )
- num_b[i] = num_b[i-nTimes];
- else //低位置0
- num_b[i] = 0;
- }
- n=m;
-
- for( j=0; j<=nTimes; j++ ) //重复调用,同时记录减成功的次数,即为商
- {
- while((nTemp = SubStract(num_a,m,num_b + j,n - j)) >= 0)
- {
- m = nTemp; //结果长度
- num_c[nTimes-j]++;//每成功减一次,将商的相应位加1
- }
- }
- if(nTemp<0)
- *p=m; // 有余数
- else
- *p=0; //无余数
-
- // 计算商的位数,并将商放在c数组中
- for(i = MAX-1; num_c[i] == 0 && i >= 0; i-- ); //跳过高位0,获取商的位数
- if(i >= 0)
- len = i + 1; // 保存位数
- for(j = 1; i >= 0; i--, j++) // 将结果复制到c数组中
- {
- c[j] = num_c[i];
- }
- return len+1; // 返回商的位数
- }
- //功能说明:主函数,调用其余函数,计算相应功能的值并输出
- int main()
- {
- //积的位数最多是因数位数的两倍
- int a[MAX]={0}, b[MAX]={0}, c[2*MAX+1]={0}, Temp[MAX]={0};
- int m,n;
- int *p1,*p2;
- int i, j;
- int select;
- int len;
- int remainder;
- p1=&m;
- p2=&n;
- while(1)
- {
- for(i=0;i<MAX;i++) // 初始化0,避免影响下一次运行
- {
- a[i]=0;
- b[i]=0;
- c[i]=0;
- Temp[i]=0;
- }
- for(;i<2*MAX+2;i++) // 初始化0,避免影响下一次运行
- {
- c[i]=0;
- }
- menu(); // 仅输出提示信息
- select=getchar(); // 获得四则运算中的一个(1加2减3乘4除0退出)
- getchar(); // 处理选择时候的回车,避免第二次运行无法重新选择0~4
- if(select =='0')
- return 0; // 退出程序
- else if(!(select>'0'&&select<'5'))
- {
- printf("输入错误!\n请从0~4中选择一个数输入!!\n\n");
- continue;
- }
- init(a,b,p1,p2); // 获取两个数值
- switch(select)
- {
- case '1':
- {
- if(a[1]==0&&b[1]==0) // 两0相加
- {
- printf("a+b=0\n\n");
- break;
- }
- printf("a+b=");
- if(a[0]==b[0]) // 同号相加则调加
- {
- j=plus(a, b, c, m, n); //加法运算
- if(c[0]!=0)
- printf("-");
- for(i=1;i<j;i++)
- printf("%d",c[i]);
- printf("\n\n");
- break;
- }
- if(a[0]==0 && b[0]!=0) // +-相加则将-变+再调减
- {
- b[0]=0; // 将b的符号变为+
- j=minus(a, b, c, m, n); //减法运算
- if(c[0]!=0)
- printf("-");
- for(i=1;i<j;i++)
- printf("%d",c[i]);
- printf("\n\n");
- break;
- }
- // -+相加,将-变+,再调换成+-,再调减
- {
- a[0]=0; // 将-变+
- // 交换a,b数值
- for(i=1; i<(m>n?m:n); i++)
- {
- Temp[i]=a[i];
- a[i]=b[i];
- b[i]=Temp[i];
- }
- // 交换a,b位数
- i=m;
- m=n;
- n=i;
- j=minus(a, b, c, m, n); //减法运算
- if(c[0]!=0)
- printf("-");
- for(i=1;i<j;i++)
- printf("%d",c[i]);
- printf("\n\n");
- break;
- }
- }
- case '2':
- {
- if(a[1]==0&&b[1]==0) // 两0相减
- {
- printf("a-b=0\n\n");
- break;
- }
- printf("a-b=");
- if(a[0]==0&&b[0]==0) // ++相减则调减
- {
- j=minus(a, b, c, m, n); //减法运算
- if(c[0]!=0)
- printf("-");
- for(i=1;i<j;i++)
- printf("%d",c[i]);
- printf("\n\n");
- break;
- }
- if(a[0]==0&&b[0]!=0) // +-相减则将-变+再调加
- {
- b[0]=0; // 将b的符号变为+
- j=plus(a, b, c, m, n); //加法运算
- if(c[0]!=0)
- printf("-");
- for(i=1;i<j;i++)
- printf("%d",c[i]);
- printf("\n\n");
- break;
- }
- if(a[0]!=0&&b[0]==0) // -+相减则将+变-再调加
- {
- b[0]='-'; // 将b的符号变为-
- j=plus(a, b, c, m, n); //加法运算
- if(c[0]!=0)
- printf("-");
- for(i=1;i<j;i++)
- printf("%d",c[i]);
- printf("\n\n");
- break;
- }
- // --相减,将-变+再交换ab值,再调减
- {
- a[0]=0; // 将-变+
- b[0]=0;
- // 交换a,b数值
- for(i=1; i<(m>n?m:n); i++)
- {
- Temp[i]=a[i];
- a[i]=b[i];
- b[i]=Temp[i];
- }
- // 交换a,b位数
- i=m;
- m=n;
- n=i;
- j=minus(a, b, c, m, n); //减法运算
- if(c[0]!=0)
- printf("-");
- for(i=1;i<j;i++)
- printf("%d",c[i]);
- printf("\n\n");
- break;
- }
- }
- case '3':
- {
- if(a[1]==0||b[1]==0) // 任意个0相乘
- {
- printf("a*b=0\n\n");
- break;
- }
- printf("a*b=");
- if((a[0]==0&&b[0]!=0)||(a[0]!=0&&b[0]==0)) // 异号相乘结果添'-'号,ab符号设为+,运算中符号不起作用
- printf("-");
- a[0]=0;
- b[0]=0;
- j=multi(a, b, c, m, n); //正整数乘法运算
- for(i=1;i<j;i++)
- printf("%d",c[i]);
- printf("\n\n");
- break;
- }
- case '4':
- {
- if(b[1]==0) // 除数为0
- {
- printf("输入错误!!\n除数不能为0!!!\n\n");
- break;
- }
- else if(a[1]==0) //被除数为0
- {
- printf("a÷b=0\n\n");
- break;
- }
- printf("a÷b=");
- if((a[0]==0&&b[0]!=0)||(a[0]!=0&&b[0]==0)) // 异号相除结果添'-'号,ab符号设为+,运算中符号不起作用
- printf("-");
- len = Division(a, b, c, m, n, &remainder, Temp);
- //输出结果
- if( len>0 )
- {
- for(i = 1; i < len; i++ )
- printf("%d", c[i]);
- if(remainder>0) // 有余数,输出余数
- {
- printf("……");
- for(i=remainder-1; i>0; i--)
- printf("%d", Temp[i]);
- }
- }
- else
- {
- printf("0……");
- for(i = 1; i < m; i++ )
- printf("%d", a[i]);
- }
- printf("\n\n");
- break;
- }
- }
- }
- return 0;
- }
复制代码
|
评分
-
查看全部评分
|