高精度（大数运算）

高精度算法

• 1.什么是高精度（别看直接跳过)
• 2.高精度乘法
• 3.高精度加法(用不考虑进制的方法最好）
• 3.高精度减法
• 5.高精度除法（先不写了，下一篇博客和快速幂一起写，现在要打游戏了嘿嘿）

1.什么是高精度（别看直接跳过)

高精度，高精度，顾名思义，就是很高的精度。。咳，实际上，在实际应用中，我们对于数字的使用，大概在千万以内就足够了，比如算人数，数钱，称重量等等，，，但是在数学领域，动辄上亿上亿亿上亿亿亿亿亿亿。。。这时候就要高精度了。因为计算机最大的内置类型unsigned long long int也才只有16个字节，也就是0-2^128.

类型	取值范围
char	-128~127
unsigned char	0~256
int	-2,147,483,648~2,147,483,647（-231 ~ 231-1）
unsigned int	0~4,294,967,295
long int	-2,147,483,648~2,147,483,647（-231 ~ 231-1）
unsigned long int	0~4,294,967,295
long long int	-9223372036854775808～+9223372036854775807
unsigned long long int	0 ～ 18446744073709551615

会发现，虽然unsigned long long int 已经很大了，但是也只有千万亿亿。如果要解决万亿亿亿亿的问题，那这是远远不够的。所以高精度的作用就是利用某种规则来计算非常大且计算机内置类型无法计算的数

2.高精度乘法

如果要算：999999989*8888888788，朋友们可以用代码试一试，估计是不行的，但是非要算出来，那么怎么办呢？
下面用一个简单的代码说明:

#include
#include
#include
using namespace std;

char s[10000];    //数组s用来存储答案
char a[10000];   //目的算a*b
char b[10000];
int main()
{
	cin >> a;  //输入a
	cin >> b;    //输入b
	int a_length = strlen(a);  //字符串a的长度
	int b_length = strlen(b);   //字符串b的长度
	int s_length = 0;
	for (int i = 0; i < a_length/2; i++)   //因为乘法是从低位开始，所以将字符串翻转
	{
		char temp;
		temp = a[i];  
		a[i] = a[a_length - i - 1];
		a[a_length - i - 1] = temp;
	}
	for (int i = 0; i < b_length/2; i++)
	{
		char temp;
		temp = b[i];
		b[i] = b[b_length - i - 1];
		b[b_length - i - 1] = temp;
	}
	for (int i = 0; i < a_length; i++)  //将字符换数字
		a[i] -= 48;
	for (int i = 0; i < b_length; i++)
		b[i] -= 48;

	//这样预处理工作就做完了，开始正式 *** 作，这里用我一开始的代码，后面有一种更好的方法。看个人习惯吧
	for (int i = 0; i < a_length; i++)  //这里数组a放在乘法式子的下面，比如123*234，a是234.
	{
		//123*234=123*4+123*30+123*200.也就是a的每个位的数分别去乘上b的整体，得到三行(个)值，然后这三行(个）错位相加即可
		int jinzhi_add = 0;   //由加法得到的进位数
		int jinzhi_mul = 0;   //由乘法得到的进位数
		int jinzhi_sum = 0;   //总的进位数
		int z = i;
		for (int j = 0; j < b_length;j++,z++)
		{
			int temp;
			temp = (s[z] + (a[i] * b[j]) % 10 + jinzhi_sum) % 10;   //temp存放当前更新完的s[z]的值
			jinzhi_add = (s[z] + (a[i] * b[j]) % 10 + jinzhi_sum) / 10;
			jinzhi_mul = (a[i] * b[j]) / 10;
			jinzhi_sum = jinzhi_add + jinzhi_mul;  //最终的要进给高位的总数
			s[z] = temp;
		}
		while (jinzhi_sum > 0)  //如果进制到最高位还有多，那么把进制放进更高位
		{
			s[z++] = jinzhi_sum % 10;
			jinzhi_sum /= 10;
		}
		s_length = z;  //更新s的长度
	}
	if (s[s_length - 1] != 0)  //防止0*0这种情况
		printf("%d", s[s_length - 1]);
	for (int i = s_length - 2; i >= 0; i--)  //逆序输出
		printf("%d", s[i]);
	return 0;
}

像这种做法，就是纯模拟了，代码非常单纯简单，但是写的时候非常费力，很不好。费力的地方就是对进位数的处理，那可不可以不处理呢？答案是可以，将进位数放在最后处理，这样简单直观且高效

#include
#include
#include
using namespace std;

int s[10000];    //数组s用来存储答案  //注意int来存数，因为不考虑进制，每个数组元素放的数可能比较大哦
char a[10000];   //目的算a*b
char b[10000];
int main()
{
	cin >> a;  //输入a
	cin >> b;    //输入b
	int a_length = strlen(a);  //字符串a的长度
	int b_length = strlen(b);   //字符串b的长度
	int s_length = 0;
	for (int i = 0; i < a_length / 2; i++)   //因为乘法是从低位开始，所以将字符串翻转
	{
		char temp;
		temp = a[i];
		a[i] = a[a_length - i - 1];
		a[a_length - i - 1] = temp;
	}
	for (int i = 0; i < b_length / 2; i++)
	{
		char temp;
		temp = b[i];
		b[i] = b[b_length - i - 1];
		b[b_length - i - 1] = temp;
	}
	for (int i = 0; i < a_length; i++)  //将字符换数字
		a[i] -= 48;
	for (int i = 0; i < b_length; i++)
		b[i] -= 48;
	//这之前都是一样的 *** 作
	for (int i = 0; i < a_length; i++)
		for (int j = 0; j < b_length; j++)
		{
			s[i + j] = s[i + j] + a[i] * b[j];    //不进行进制转换，下面给个图帮助理解
		}
	//然后要进制转换，那么首先要知道s数组的长度
	//如果a是n位数，b是m位数，那么s就是n+m-1位数（不考虑进制，就是每一位数实际上都是一个“多位数”，下面会给一个图帮助理解.
	s_length = a_length + b_length - 1;
	for (int i = 0; i < s_length; i++)
	{
		s[i + 1] = s[i + 1] + s[i] / 10;
		s[i] = s[i] % 10;
	}
	while (s[s_length] >0)  //本来s[i]的长度是s_length,但是s[s_length-1]可能进位给s[s_length]
	{
		s[s_length + 1] += s[s_length] / 10;
		s[s_length] %= 10;
		s_length++;
	}
	//然后特殊判断一下
	//0*0这种类型有0的情况
	while (s[s_length-1] == 0&&s_length>1)
		s_length--;
	for (int i = s_length-1; i >= 0; i--)
	{
		printf("%d", s[i]);
	}
	return 0;
}

3.高精度加法(用不考虑进制的方法最好）

//这是我习惯的写法，不考虑进制的方法道友们自己尝试写一下，自己写的才是自己的。
#include
#include
#include
using namespace std;

char a[100000];   //实现a+b 
char b[100000];

int main()
{
	scanf("%s",a);
	scanf("%s",b);
	int a_len=strlen(a);
	int b_len=strlen(b);
	int max_len=(a_len>b_len)?a_len:b_len;
	for(int i=0;i<a_len/2;i++)
	{
		char temp=a[i];
		a[i]=a[a_len-i-1];
		a[a_len-i-1]=temp;
	}
	
	for(int i=0;i<a_len;i++)
	{
		a[i]-=48;
	}	
	
	for(int i=0;i<b_len/2;i++)
	{
		char temp=b[i];
		b[i]=b[b_len-i-1];
		b[b_len-i-1]=temp;
	}
	
	for(int i=0;i<b_len;i++)
	{
		b[i]-=48;
	}
	
	int jinzhi=0;
	int i=0;
	for(i=0;i<max_len;i++)
	{
		int temp=(a[i]+b[i]+jinzhi)/10;
		a[i]=(a[i]+b[i]+jinzhi)%10;
		jinzhi=temp;
	}
	if(jinzhi>0)
	{
		a[i++]=jinzhi%10;
		jinzhi/=10;
	}
	a_len=i;
	while(a[a_len-1]==0&&a_len>1)
		a_len--;
	for(int i=a_len-1;i>=0;i--)
		printf("%d",a[i]);
	return 0;
}

3.高精度减法

思路是这样的:因为小学数学老师黄老师说，用竖式减法的时候，要把大的数放上面，小
的数放下面，否则会算不出来。那么根据黄老师的思路，我们第一步就是想办法把大的数放上面，然后按照简单的借位相减就ok了，最后判断一下符号。

#include
#include
#pragma warning (disable:4996)
char a[100000];
char b[100000];
int long_s[100000];   //存放大的数组 
int short_s[100000];    //存放小数组 
int cmp_a_b(char* a, int a_len, char* b, int b_len)   //比较a和b谁大 
{
	int max = (a_len > b_len) ? a_len : b_len;
	for (int i = max - 1; i >= 0; i--)
	{
		if (a[i] != b[i])
		{
			if (a[i] > b[i])   //a大于b返回1 
				return 1;
			else
				return -1;   //b大于a返回-1 
		}
	}
	return 0;   //a==b返回0 
}

int main()
{
	scanf("%s", a);
	scanf("%s", b);
	int a_len = strlen(a);
	int b_len = strlen(b);
	int longer = (a_len >= b_len) ? a_len : b_len;
	int zheng_fu = 0;   //符号
	if (cmp_a_b(a, a_len, b, b_len) >= 0)  //a大于等于b ,则a放减法竖式的上面，b放下面，符号减法运算规则 
	{
		zheng_fu = 1;//a-b大于等于0，答案是正数 
		for (int i = 0; i < a_len; i++)
		{
			long_s[i] = a[a_len - 1 - i] - 48;
		}
		for (int i = 0; i < b_len; i++)
		{
			short_s[i] = b[b_len - i - 1] - 48;
		}
	}
	else    //b大于a，b放减法竖式的上面，a放下面，符合减法运算规则 
	{
		zheng_fu = 0;  //答案是负数 
		for (int i = 0; i < a_len; i++)
		{
			short_s[i] = a[a_len - 1 - i] - 48;
		}
		for (int i = 0; i < b_len; i++)
		{
			long_s[i] = b[b_len - i - 1] - 48;
		}
	}

	//上面的预处理完毕，下面开始正式运算
	int jiewei = 0;  //减法的借位
	for (int i = 0; i < longer; i++)
	{
		if (long_s[i] + jiewei - short_s[i] < 0)//需要借位 
		{
			long_s[i] = (long_s[i] + 10 + jiewei - short_s[i]) % 10;
			jiewei = -1;
		}
		else  //不需要借位 ,long[i]+jiewei-short[i]>=0 
		{
			long_s[i] = (long_s[i] + jiewei - short_s[i]) % 10;
			jiewei = 0;
		}
	}

	//最终long数组保存的结果就是最终结果的绝对值，还加正负
	if (zheng_fu == 0)
	{
		printf("-");
	}
	while (long_s[longer - 1] == 0 && longer > 1)  //排除最高位是0
	{
		longer -= 1;
	}
	for (int i = longer - 1; i >= 0; i--)
		printf("%d", long_s[i]);
	return 0;

}

5.高精度除法（先不写了，下一篇博客和快速幂一起写，现在要打游戏了嘿嘿）

我来了！！（tmorrom）

#include
#include
#pragma warning (disable:4996)
char a[10000];
char b[10000];
int big[10000];
int small[10000];
int ans[10000];
int yushu = 0;  //设置一个变量看有没有余数 
int num = 0;
int cmp_a_and_b(char* a, char* b, int longer)   //比较a和b谁大一点，a大返回1，b大返回-1，a==b返回0 
{
	for (int i = longer - 1; i >= 0; i--)
	{
		if (a[i] != b[i])
		{
			if (a[i] > b[i])
				return 1;
			else
				return -1;
		}
	}
	return 0;
}


void copy_a_b(char* a, int a_len, char* b, int b_len)  //将数组a，b逆序存入big和small数组 
{
	for (int i = 0; i < a_len; i++)
	{
		big[i] = a[a_len - i - 1] - 48;
	}
	for (int i = 0; i < b_len; i++)
	{
		small[i] = b[b_len - i - 1] - 48;
	}
}

int judge(int* a, int a_len, int* b)  //单纯比较a，b大小 
{
	for (int i = a_len - 1; i >= 0; i--)
	{
		if (a[i] != b[i])
		{
			if (a[i] > b[i])
				return 1;
			else
			{
				yushu = 1;
				return -1;
			}

		}
	}
	return 1;
}

int main()
{
	//除法，先规定是什么样的除法，这里规定，如果除不尽，那么要把余数算出来，如果除的尽，不用写余数
	//那么我的思路是：（1）先找到大的数  （2）大的数减去小的数，可以完全减去一个小的数，那么加1  （3）直到大数不再可以完全减去小数，此时大数就是结果的余数
	//（4）把减去小数的个数累加得到的就是最后的商，然后大数剩下的数就是余数。
	//因此需要3个数组，分别存放除数，被除数，商。 
	scanf("%s", a);
	scanf("%s", b);
	int a_len = strlen(a);
	int b_len = strlen(b);
	int longer = (a_len > b_len) ? a_len : b_len;
	int ans_len = 0;
	//对0%0这种类似情况特判
	/*if (a[a_len - 1] == '0' || b[b_len - 1] == '0')
	{
		printf("0");
		return 0;
	}*/
	switch (cmp_a_and_b(a, b, longer))   //switch游戏机是任天堂研制开发并于2017年上市的游戏机，第一周销量达到150万台，首发护航大作《塞尔达传说》更是风靡全球，火爆全球，成为开放式游戏的鼻祖 
	{
	case 1:  //a>b
	{
		copy_a_b(a, a_len, b, b_len);
		break;
	}
	case 0:   //a==b
	{
		printf("1");
		return 0;
	}
	case -1:  //b>a
	{
		copy_a_b(b, b_len, a, a_len);
		break;
	}
	default:
	{
		break;
	}
	}
	while (judge(big, longer, small) == 1)  //big>=small
	{
		printf("%d ", num++);
		int jiewei = 0;   //借位 
		for (int i = 0; i < longer; i++)
		{
			if (big[i] + jiewei < small[i])
			{
				big[i] = (big[i] + 10 + jiewei - small[i]) % 10;
				jiewei = -1;
			}
			else
			{
				big[i] = (big[i] + jiewei - small[i]) % 10;
				jiewei = 0;
			}
		}

		int jinzhi = 0;
		for (int i = 0; i <= ans_len; i++)
		{
			if (i == 0)
			{
				int temp = (ans[i] + 1) / 10;
				ans[i] = (ans[i] + 1) % 10;
				jinzhi = temp;
			}
			else
			{
				int temp = (ans[i] + jinzhi) / 10;
				ans[i] = (ans[i] + jinzhi) % 10;
				jinzhi = temp;
			}
		}
		if (jinzhi > 0)
		{
			ans[++ans_len] = jinzhi % 10;
			jinzhi /= 10;
		}
	}

	for (int i = ans_len; i >= 0; i--)
	{
		printf("%d", ans[i]);
	}
	while (big[longer - 1] == 0 && longer > 1)
	{
		longer--;
	}
	printf(".....");
	for (int i = longer - 1; i >= 0; i--)
		printf("%d", big[i]);
	return 0;
}