当前位置: 代码迷 >> 综合 >> 大数 高精度 四则运算
  详细解决方案

大数 高精度 四则运算

热度:18   发布时间:2023-12-10 07:52:48.0

大数的四则运算

高精度计算,是指参与运算的数大大超出了标准数据类型所能表示的范围,例如两个1000位数相乘,这类题目在算法竞赛中出现得很频繁。在c或者c++中,最大数据类型只有64位,如果需要处理更大的数,只能用数组模拟,把大数的每一位存储在数组中,然后按位处理进位、借位。
在网上搜索了一番资料,发现写的都过于繁琐、不易理解,笔者写了大数的四则运算,挺易懂的,与大家分享。
首先定义一个结构体

typedef struct bign{
    int num[MAXN];			//高低位反着存储各位的数字 int len;				//数字的位数 bign(){
    memset(num,0,sizeof(num));len=-1;}		//构造函数 
}bignum;

注意,该结构里有一个num[ ]数组,存储的数字高低位是相反的,如1234,数组中实际是num[0]=4,num[1]=3,num[2]=2,num[3]=1,这样做有助后续的运算操作,因为加减法都是从低位开始的。len代表着该数字的位数。

将字符串转换为大数的函数

bignum change_bignum(char *s){
    bignum tmp;int length=strlen(s);for(int i=0;i<strlen(s);i++)tmp.num[length-1-i]=s[i]-48;		//高位在后,低位在前,方便运算 tmp.len=length;return tmp;
}

该函数的参数是字符指针,在主函数中,只要在字符数组中赋值以后,就可以调用change_bignum()函数,然后返回一个bignum类型的结构体。再强调一下,大数的高低位是相反的。

打印大数的函数

void show(bignum a){
    		//打印数字 for(int i=a.len-1;i>=0;i--)printf("%d",a.num[i]);	printf("\n");
}

注意,即使运算完成以后,也只能通过数组来输出,因为就算long long也没有这么大。(减法,除法可能得到一个小的数,但是很特殊)
准备工作做完了就可以做运算了。
加法运算

bignum add(bignum a,bignum b){
    bignum tmp;int carry=0;			//进位信息 int length=max(a.len,b.len); 	//两个数的最大位数 for(int i=0;i<length;i++){
    tmp.num[i]=(a.num[i]+b.num[i]+carry)%10;	//存储做完运算后的数字 carry=(a.num[i]+b.num[i]+carry)/10;			//更新进位信息 }if(carry){
    			//如果最后一次运算以后还有进位 tmp.num[length]=carry;	//最高位就是进位数字 tmp.len=length+1;		//新的数字位数加1 }elsetmp.len=length;			//新数字的位数 return tmp;
}

思想就是从低位开始相加,如果大于10,就用carry存储进位信息,然后把相加的结果mod10,存在相应的位置上。如果相加结果大于10,carry可以直接赋值1,为什么呢,因为两个小于10的数字相加,最大就是18,也只能进一位,但是用相加的结果除10更好,因为在后面的乘法运算中,进位信息可能是2,3,4…比如7*7,要进4。最后的if,else来给新的大数赋值长度,一般来说就是两个加数中位数最多的那一个,但两个位数相同的数相加以后在最高位可能产生进位信息,就要把大数的长度加一位,比如77+66。

减法运算

bignum Minus(bignum a,bignum b){
    			//a比b大 bignum tmp;for(int i=0;i<a.len;i++){
    if(a.num[i]<b.num[i]){
    int borrow=1;			//借位信息 while(a.num[i+borrow]==0)		//高位都是0,直到找到可以借位的数字 borrow++;a.num[i+borrow]--;		//被借的位数减1 a.num[i]+=10;			//借位的位加10 for(int j=i+1;j<i+borrow;j++){
    		//更改那些0的高位a.num[j]=9;	 }}tmp.num[i]=a.num[i]-b.num[i];}for(int i=a.len-1;i>=0;i--)		//找到第一个最高位不为0的数作为新数的最高位 if(tmp.num[i]!=0){
    tmp.len=i+1;			//新数的位数 break;}return tmp;
}

减法较加法来说复杂(就比如除法比乘法难,博主现在也没写出来,明天更新)
加法有进位,减法就有借位,加法从最低为开始,减法亦从最低位开始。如果被减数的低位比减数的低位数值要小,就要向高位借1,如果此时高位为0,还要向再高一位借,直到高位非零,然后借位的位置数字加上10,被借位的位数值减1,中途那些0的位都变成9(比如1001 - 9),借位好了以后就可以运算了。在运算好了以后,从高位往低位遍历寻找第一个非零的位,这样就可以确定新的数字的位数了。

乘法运算

大数乘法和小学的乘法相同,列竖式计算,如上图。

bignum multiply(bignum a,bignum b){
    			//列竖式计算 bignum tmp;int carry=0;for(int i=0;i<b.len;i++){
    		//b的每一位 for(int j=0;j<a.len;j++){
    		//a的每一位 tmp.num[i+j]+=(b.num[i]*a.num[j]+carry)%10;		//乘法看成移位加法 carry=(b.num[i]*a.num[j]+carry)/10;if(tmp.num[i+j]>=10){
    		//竖式累加也可能产生进位 tmp.num[i+j]-=10;		//这里把每次运算后的结果直接与相应位数上的数字相加 carry++;				//产生进位直接给这一次竖式计算的下一位,不影响最后结果 }}}if(carry){
    		//同样,若两数最高位运算产生进位,那么新的数字的位数要加1 tmp.num[a.len-1+b.len]=carry;tmp.len=a.len+b.len;	}elsetmp.len=a.len-1+b.len;	//否则就是这样 想想1000*100 和300*400 return tmp;
}

在这里插入图片描述
第一行数字假设为a,第二行为b,b的每一位乘以a的每一位,所以有两层循环,注意a和b的每一位数字的权值是不同的,比如a的第二个数字2,b的第一个数字4,相乘的结果应该保存在十位上。a的第i位数字和b的第j位数字相乘的结果应该保存在新数的i+j位上(这里要注意num[0]是个位数字,推广一下,num[i]是i+1位数字),可以找几个数验证一下。还要注意一下,这里的进位信息有两个,一个是a的每一位和b的每一位乘法得到的进位,另一个是两个乘法中间结果相加产生的进位(图中紫色所示),解释了以后,上面的代码很易理解了。

大数除法

1 高精度除以低精度(除数可以用int或float表示)
因为可能除法除不尽,有余数,我们重新定义一个pair,来保存除法的商和余数

typedef pair<bignum, int> P2;				//用于返回商和余数

这样,函数就可以返回除法运算的商和余数了。
因为除数是一个可以用int或者float表示的数,所以这一类除法的思想是:从最高位开始,截取和除数位数相同的数字,存储在middle(为基本类型int 或 long long int)中,然后每次让middle和除数做除法,商保留在相应的位置,然后用第一次除法的余数补上bignum后一位的"进位",再和除数做除法,如此,一直到bignum的末尾。和小学的除法竖式原理相同,如下图:
在这里插入图片描述
现在bignum中(这里是522)中截取和除数(这里是12)位数相同的数,保存在middle中,所以middle一开始是52,然后用middle和除数做除法,商4,余4,接着用余数乘以10,再加上bignum后面补的一位,作为新的middle(42),然后再和除数做除法,商3,余6,注意,此时bignum中没有可以补的进位了,所以除法结束,余数就是最后一次除法的余数。
来看代码:

P2 divide_2(bignum a, int c) {
    		//P2是返回类型bignum ans;int middle = 0;			//用于中间计算int borrow = 0;		//借位信息 int wei = 0;		int tmp = c;while (tmp) {
    wei++;		//获取c的位数 tmp /= 10;}for (int i = 0; i < wei; i++)			//一开始截取和c一样位数的数字,从高位开始做除法middle = middle * 10 + a.num[a.len - 1 - i];while (1) {
    ans.num[a.len - wei - borrow] = middle / c;		//保存商middle = middle % c;if (borrow == a.len - wei)		//当大数a没有位数可以借的时候,计算结束break;middle = middle * 10 + a.num[a.len - wei- borrow-1];			//原来的结果乘以10加上后一位borrow++;			//借位加1}for (int i = a.len - wei; i >= 0; i--)		//计算商的位数if (ans.num[i] != 0) {
    ans.len = i+1;break;}return P2(ans, middle);
}

首先获取除数c的位数,存储在wei中,然后截取和wei等长的数,存在middle中(因为除数可以用基本类型表示,截取的数也一定可以用基本类型表示,笔者这里用了int,如果除数更大,需要改成long long int),注意,要在a中从后往前截取,因为a中高低位是相反的。然后就可以像除法竖式一样,让middle和除数做除法,一直到不能了为止,好,那什么时候不能再除了呢?定义一个borrow变量,代表bignum中补的位数,一开始middle截取了和除数c一样多的数字,那最多还有bignum.len-wei多的数字可以补嘛,同时,middle和除数c的商的位权(商的位置)也随着补的位数的增大而变小,(比如上图两次除法的商分别是4和3,4的位置是十位,而3的位置是个位),所以在处理商的位置的时候也要用到borrow,borrow每加1,商的位置就要减1(即往低位进1,别忘了bignum中高低位是相反的)。
PS. 每次计算商的位置,还有截取的时候那些下标的位置,很容易弄错,多了一位上了一位,最好在心里举个例子,比如123 除以 4 来模拟,一步一步调试也可

2 高精度除以高精度
这一类除法比上一类要难,因为除数也是大数,也得用bignum存储,而且大数的除法是很不方便的,这里,我们用减法替代除法,如果a除以b,商c余d,那么如果a比b大,那么a就减去b,然后商加1,如此,直到a比b小,这时候就得到余数d了。但是这样子实在太慢了,比如100除以3,要减去33次,更何况大数可以到一千位,所以需要优化。想想上面的高精度除以低精度,利用借位borrow,就可以将位权降低10倍,同理,这里我们也采用这样的算法,不过除法要用减法代替。

同样的,定义一个结构体同时返回商和余数,不过高精度和高精度的除法,余数仍然可能是高精度,所以这次两个返回值都是bignum。

typedef pair<bignum, bignum> P1;

这次还多了一个judge函数,返回值是bool,用来判断middle和除数哪一个更大,如果middle更大,就可以做除法,否则就要向后一位借位,然后再做除法。(当middle和除数一样大时,也是返回true,想想为什么)代码如下,配合注释,很容易理解。

bool judge(bignum middle, bignum b) {
    	//b是除数if (middle.len > b.len)		//当middle位数比b大时,middle肯定更大return true;else if (middle.len == b.len) {
    		//当两者位数相同时for (int i = b.len - 1; i >= 0; i--) {
    		//从高位到低位一次比较if (middle.num[i] > b.num[i])	//如果有一个不相等就返回return true;else if (middle.num[i] < b.num[i])return false;}return true;		//两数相等 也是返回true 相当于商1,余0}elsereturn false;		//middle位数比b小 
}

然后是主要的函数了:

P1 divide(bignum a, bignum b) {
    bignum ten;					//用于计算除法时借位时扩大十倍ten.len = 2; ten.num[0] = 0; ten.num[1] = 1;		//初始化10bignum ans;			//商bignum middle;		//中间过程 int shang_pos = a.len - b.len;		//第一位商的位置 int k = 0;			//middle借位的次数 最多a.len-b.len for (int i = b.len - 1; i >= 0; i--) {
    		//初始化middle 在a中截取b位 middle.num[i] = a.num[a.len - (b.len - 1 - i) - 1];}middle.len = b.len;while (1) {
    while (judge(middle, b)) {
    			//判断middle是否b大 ans.num[shang_pos - k]++;middle = Minus(middle, b);}if (k == a.len - b.len)break;middle = multiply(middle, ten);bignum gewei;			//模拟借的那一位gewei.len = 1; gewei.num[0] = a.num[a.len - b.len - k - 1];middle = add(middle, gewei);k++;		//借位}for (int i = shang_pos; i >= 0; i--)if (ans.num[i] != 0) {
    ans.len = i + 1;break;}return P1(ans,middle);
}

前两行定义了一个bignum类型的变量ten,顾名思义,就是把10用bignum来存,便于后续计算,稍后讲解。shang_pos来存放每一次计算商的位置,先计算好了第一次运算的位置,后面随着borrow的增加会左移(减1)。和低精度一样,先从最高位高位截取指定长度存在middle中,然后判断middle和除数b谁大,如果middle更大,就减去除数,同时指定位置的商要加1(模拟除法),直到middle比b小,这时候需要借下一位,具体的操作是:自身先乘以十(可以使用之前封装好的multiply函数,不过10也要用到bignum类型,你看,我们第一步就做好了),然后加上借的那一位(是在最低位上,就是个位),定义了bignum ccc,来存储个位上的数值,然后又可以调用封装好的函数add()实现相加操作。一轮之后borrow要加1,当borrow最大,也就是等于除数和被除数之差的时候,break,此时middle存储的数就是余数,最后利用pair返回就行了。大体上和低精度差不多,就是middle和除数的操作,用减法操作模拟较容易。

完整代码如下:

// Raymond Feb 14th,2020
#include<bits/stdc++.h>
using namespace std;const int MAXN = 1000;
typedef struct bign {
    int num[MAXN];			//高低位反着存储各位的数字 int len;				//数字的位数 bign() {
     memset(num, 0, sizeof(num)); len = -1; }		//构造函数 
}bignum;
typedef pair<bignum, bignum> P1;
typedef pair<bignum, int> P2;				//用于返回商和余数bignum change_bignum(char *s) {
    bignum tmp;int length = strlen(s);for (int i = 0; i < strlen(s); i++)tmp.num[length - 1 - i] = s[i] - 48;		//高位在后,低位在前,方便运算 tmp.len = length;return tmp;
}
bignum add(bignum a, bignum b) {
    bignum tmp;int carry = 0;			//进位信息 int length = max(a.len, b.len); 	//两个数的最大位数 for (int i = 0; i < length; i++) {
    tmp.num[i] = (a.num[i] + b.num[i] + carry) % 10;	//存储做完运算后的数字 carry = (a.num[i] + b.num[i] + carry) / 10;			//更新进位信息 }if (carry) {
    			//如果最后一次运算以后还有进位 tmp.num[length] = carry;	//最高位就是进位数字 tmp.len = length + 1;		//新的数字位数加1 }elsetmp.len = length;			//新数字的位数 return tmp;
}
bignum Minus(bignum a, bignum b) {
    			//a比b大 bignum tmp;for (int i = 0; i < a.len; i++) {
    if (a.num[i] < b.num[i]) {
    int borrow = 1;			//借位信息 while (a.num[i + borrow] == 0)		//高位都是0,直到找到可以借位的数字 borrow++;a.num[i + borrow]--;		//被借的位数减1 a.num[i] += 10;			//借位的位加10 for (int j = i + 1; j < i + borrow; j++) {
    		//更改那些0的高位a.num[j] = 9;					//比如101-99 101的十位变成9 }}tmp.num[i] = a.num[i] - b.num[i];}for (int i = a.len - 1; i >= 0; i--)		//找到第一个最高位不为0的数作为新数的最高位 if (tmp.num[i] != 0) {
    tmp.len = i + 1;			//新数的位数 break;}return tmp;
}
void show(bignum a) {
    		//打印数字 for (int i = a.len - 1; i >= 0; i--)printf("%d", a.num[i]);printf("\n");
}
bignum multiply(bignum a, bignum b) {
    			//列竖式计算 bignum tmp;int carry = 0;for (int i = 0; i < b.len; i++) {
    		//b的每一位 for (int j = 0; j < a.len; j++) {
    		//a的每一位 tmp.num[i + j] += (b.num[i] * a.num[j] + carry) % 10;		//乘法看成移位加法 carry = (b.num[i] * a.num[j] + carry) / 10;if (tmp.num[i + j] >= 10) {
    		//竖式累加也可能产生进位 tmp.num[i + j] -= 10;		//这里把每次运算后的结果直接与相应位数上的数字相加 carry++;				//产生进位直接给这一次竖式计算的下一位,不影响最后结果 }}}if (carry) {
    		//同样,若两数最高位运算产生进位,那么新的数字的位数要加1 tmp.num[a.len - 1 + b.len] = carry;tmp.len = a.len + b.len;}elsetmp.len = a.len - 1 + b.len;	//否则就是这样 想想1000*100 和300*400 return tmp;
}bool judge(bignum middle, bignum b) {
    if (middle.len > b.len)return true;else if (middle.len == b.len) {
    for (int i = b.len - 1; i >= 0; i--) {
    if (middle.num[i] > b.num[i])return true;else if (middle.num[i] < b.num[i])return false;}return true;		//两数相等 }elsereturn false;		//middle位数比b小 
}P1 divide(bignum a, bignum b) {
    bignum ten;					//用于计算除法时借位时扩大十倍ten.len = 2; ten.num[0] = 0; ten.num[1] = 1;		//初始化10bignum ans;bignum middle;		//中间过程 int shang_pos = a.len - b.len;		//第一位商的位置 int k = 0;			//middle借位的次数 最多a.len-b.len for (int i = b.len - 1; i >= 0; i--) {
    		//初始化middle 在a中截取b位 middle.num[i] = a.num[a.len - (b.len - 1 - i) - 1];}middle.len = b.len;while (1) {
    while (judge(middle, b)) {
    			//判断middle是否b大 ans.num[shang_pos - k]++;middle = Minus(middle, b);}if (k == a.len - b.len)break;middle = multiply(middle, ten);bignum gewei;gewei.len = 1; gewei.num[0] = a.num[a.len - b.len - k - 1];middle = add(middle, gewei);k++;		//借位}for (int i = shang_pos; i >= 0; i--)if (ans.num[i] != 0) {
    ans.len = i + 1;break;}return P1(ans,middle);
}P2 divide_2(bignum a, int c) {
    bignum ans;int middle = 0;			//用于中间计算int borrow = 0;		//借位信息 int wei = 0;		int tmp = c;while (tmp) {
    wei++;		//获取c的位数 tmp /= 10;}for (int i = 0; i < wei; i++)			//一开始截取和c一样位数的数字,从高位开始做除法middle = middle * 10 + a.num[a.len - 1 - i];while (1) {
    ans.num[a.len - wei - borrow] = middle / c;middle = middle % c;if (borrow == a.len - wei)		//但大数a没有位数可以借的时候,计算结束break;middle = middle * 10 + a.num[a.len - wei- borrow-1];			//原来的结果乘以10加上后一位borrow++;			//借位加1}for (int i = a.len - wei; i >= 0; i--)		//计算商的位数if (ans.num[i] != 0) {
    ans.len = i+1;break;}return P2(ans, middle);
}int main() {
    bignum a, b, result;char s[MAXN];scanf("%s", s);a = change_bignum(s);scanf("%s", s);b = change_bignum(s);result = add(a, b);			//加法printf("Add:\t");show(result);result = multiply(a, b);	//乘法printf("Multi:\t");show(result);result = Minus(a, b);		//减法printf("Minus:\t");show(result);P1 result_1;result_1 = divide(a, b);printf("Divide:\t");show(result_1.first);		//除法printf("\t");show(result_1.second);//int c;//P2 result_2;//scanf("%d", &c);//result_2 = divide_2(a, c);//show(result_2.first);//printf("%d\n", result_2.second);return 0;
}

以上为个人见解,如有不对,请指出(编程小白不需要面子呀),欢迎大家一起讨论。