大整數(25000位)的四則運算C語言源程序

ID:166089 · 發表于 2018-7-2 10:43

研究密碼學過程中，遇到數據位比較長，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;
}