• C++不知算法系列之高精度数值处理算法

    1. 前言

    什么是高精度数值处理算法？

    高精度数值指因受限于计算机硬件的制约，超过计算机所能存储范围的数值。既然不能存储，更谈不上运算。

    对此类数值的加、减、乘、除运算需要提供针对性的算法方能获取到结果。此类算法的设计思路因有别于其它算法，为了研究的方便，称此类算法为高精度数值处理算法。

    本文将讲解如何实现对此类数值的加、减、乘、除运算。

    2. 高精度数值的运算

    对高精度数值运算时，需要从 2 个方面入手：

    • 如何存储：其基本存储思想是把数值以字符串的形式输入，然后转储于整型类型的数组中。理论上，数组的长度是不受限制的，或者采用一部分一部分的处理方式。
    • 如何计算：基本计算思想是把计算的2个数值以数组形式存储后，以逐位逐位地方式进行计算。如此，把大问题化解成了小问题。

    2.1 高精度的加法

    高精度数值相加的思路：

    • 用整型数组存储 2 个加数。为了遵循数组从头指针向尾指针扫描的使用习惯，存储时，可以把低位存储在前面，高位存储存在后面，至于是否如此存储可以根据实际设计的算法决定。如下存储 374和65。
    //加数一
int num1[100]={4,7,3,0,0……};
//加数二
int num2[100]={5,6,0,0……};
//相加结果,初始化为 0
int result[100]={0};
//存储两数相加的进位
int jinWei=0;

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 遍历数组，对 2 个数组的对应位进行相加。如num1[0]+num2[0]，且把相加结果存储到 result[0]位置。相加时，需要根据加法运算法则，考虑进位和不进位两种情况。

    不进位情况：如 num1[0]+num2[0]=4+5不需要进位，直接把结果存储到 result[0]中。

    1.png

    进位情况：如num1[1]+num2[1]=7+6=13。有进位操作，则把结果的余数存储在result[1]=3中。把结果的商（进位值）临时存储在变量jinWei中。

    2.png

    最后，num1[2]+num2[2]+jinWei=3+0+1=4存储在result[2]中。

    3.png

    通用逻辑：

    加数一和加数二对应位中的值和进位变量中的值一起相加，结果的余数存储在结果数组中，商存储在进位变量中。

    编码实现：

    #include 
#include 
using namespace std;
int main(int argc, char** argv) {
	//存储加数一(被加数),初始为 0
	int num1[100]= {0};
	//加数一的长度
	int numLen1=0;
	//存储加数二（加数），初始为 0
	int num2[100]= {0};
	//加数二的长度
	int numLen2=0;
	//存储结果
	int result[100]= {0};
	//存储进位值
	int jinWei=0;
	//加数一的字符串格式
	string numStr1;
	//加数二的字符串格式
	string numStr2;
	//输入加数一
	cout<<"请输入加数一："<>numStr1;
	//转存至数组中(低位存储在数组的前面)
	numLen1= numStr1.size();
	for(int i=0; i>numStr2;
	numLen2=numStr2.size();
	//转存至数组中(反序存储)
	for(int i=0; i=numLen2?numLen1:numLen2;
	int idx=0;
	while(idx0) {
		result[idx]=jinWei;
	} else {
		idx--;
	}
    //输出
	for(int i=idx; i>=0; i--) {
		cout<
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60

    输出结果：

    23.png

    2.2 高精度的减法

    减法是加法的逆操作，加法时需要考虑进位操作， 减法时则需要考虑借位与不借位两种情况。

    • 不借位：6-5不需要借位。

    4.png

    • 借位：如下十位的 4减6，需要借位。向百位借 1 当10，4变成14。高位3变成2。

    5.png

    6.png

    7.png

    编码实现：

    #include 
#include 
using namespace std;
int main(int argc, char** argv) {
	//存储减数一(被减数),初始为 0
	int num1[100]= {0};
	//减数一的长度
	int numLen1=0;
	//存储减数二（减数），初始为 0
	int num2[100]= {0};
	//减数二的长度
	int numLen2=0;
	//存储结果
	int result[100]= {0};
	//减数一的字符串格式
	string numStr1;
	//减数二的字符串格式
	string numStr2;
	//输入减数一
	cout<<"请输入减数一："<>numStr1;
	//输入减数二
	cout<<"请输入减数二："<>numStr2;
	//转存至数组中(反序存储)
	numLen1= numStr1.size();
	for(int i=0; i=numLen2?numLen1:numLen2;
	int idx=0;
	while(idx=0; i--) {
		if(result[i]!=0)
			cout<
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53

    执行结果：

    8.png

    如上代码，对原数组中的数据会进行修改。

    也可以如下实现：使用一个借位标志变量，用来标识对某位进行计算时，是否借过位。

    #include 
#include 
using namespace std;
int mai123n(int argc, char** argv) {
    //省略……
    //是否借位标志信息
	int jieWei=0;
	int idx=0;
	while(idx

虽然不会修改原数组中的数字，但逻辑有点累赘。

Tips：如上算法，需要保证大数减小数。

2. 3 高精度的乘法

商精度数值相乘可以有 2 种参考方案，如计算 246*65：

2.3.1 方案一
2.3.2 方案二

方案二和方案一同工异曲，不借助额外的空间存储数据，使用结果数组存储中间计算数值，也存储最终结果数值。不产生额外的空间使用代价。

在高精度乘法时，有一个位置关系需要了解。如nums1[100]={6,4,2}，nums[100]={5,6}，当使用result[100]存储最终相乘结果时，nums1[i]*nums2[j]的结果存储在 result[i+j]中。

**Tips：**从数学法则可知，当 2 数两乘时，百位乘以十位的值要存储在结果的千位上。

9.png

10.png

继续：4*6=24，加上原来的值3，再加上进位值2，最终结果是 29 ,取余数 9 存储，保存进位值 2。

11.png

把最后的进位值作为进位作为结果数值存储 。

12.png

14.png

15.png

最后在结果中添加进位值。

16.png

编程实现：

#include 
#include 
using namespace std;
int main(int argc, char** argv) {
    //省略乘数的输入，和前面相加数、相减数输入的代码一样
	for(int i=0; i1)
		c--;
	for(int i=c; i>=0; i--) {
		cout<

输出结果：

17.png

2.4 高精度相除

高精度相除分 2 种情况讨论：

2.4.2 高精度除以低精度

所谓高精度除以低精度，存储每次相除的商（0~9之间），其余数和被除数后面数字相加，作为新的被除数继续做除法。

如计算 642除以5的流程：

18.png

19.png

20.png

编码实现：

#include 
#include 
using namespace std;
int main(int argc, char** argv) {
	//存储被除数,初始为 0
	int num[100]= {0};
	//除数的长度
	int numLen=0;
	//除数的字符串格式
	string numStr;
	//存储结果
	int result[100]= {0};
	//低精度数字
	int num2;
	cout<<"请输入高精度被除数："<>numStr;
	cout<<"请输入低精度除数："<>num2;
	//转存至数组中
	numLen= numStr.size();
	for(int i=0; i

输出结果：

21.png

22.png

逐位相除，效率显然是较低的，可以采用一次多位相除方案。可以自行思考。

2.4.2 高精度除以高精度

高精度除以高精度，可以把除法变成减法和加法操作。如：264 除 56的基本思路如下：

当相减的结果小于除数时，不再相减，则264 / 56结果为 4，余数为 40。如上所述，除了不间断地对 2 个数字进行相减，还要统计相减的次数。

**Tips：**从数学角度思考，乘法的本质是加法操作，除法的本质是减法操作。

**编码实现：**代码中有注释，不再另行解释。代码对相减次数做了相应的性能优化。

# include 
# include 
using namespace std;
/*
*初始化数组中的值
*/
void stringToNumber(int arr[]) {
	string snum;
	cin>>snum;
	arr[0] = snum.length();
	//用snum[0]存储数字长度
	for(int i=1; i<=arr[0]; i++)
		//将数串s转换为数组	a,并倒序存储
		arr[i] = snum[arr[0]-i] -'0';
}

/*
* 比较 2 个数字的大小
*/
int compare (int num1[],int num2[]) {
	//比较 2 个数字的位数
	if(num1[0]>num2[0]) return 1 ;
	if(num1[0]0; i--) {
		if (num1[i]>num2[i]) return 1 ;
		if (num1[i]0 && num1[num1[0]]==0)
			num1[0]--;
		return;
	}
}

//这是一个优化方案，用来减少相减次数。如 246 / 56  ，先 用 246 / 560 
void numcpy(int p[],int q[],int det) {
	for (int i=1; i<= p[0]; i++ )
		q[i + det-1] = p[i];
	q[0] = p[0] + det-1 ;
}
/*
*高精度相除
*/

void gjdChu(int num1[],int num2[],int result[]) {
	int i, tmp[101];
	result[0] = num1[0] -num2[0]+ 1;
	for (i = result[0]; i>0; i--) {
		int tmp[101]={0} //memset(tmp,0, sizeof(tmp) ) ;	//数组清零
		numcpy(num2,tmp,i);
		while(compare(num1,tmp)>=0) {
			result[i]++ ;   
			gjdJian(num1, tmp) ;
		}
	}
	while(result[0]>0&&result[result[0]]==0)result[0]--;
	return ;
}
int main(int argc, char** argv) {
	int num1[101]= {0};
	int num2[101]= {0};
	int result[101]= {0};
	stringToNumber(num1);
	stringToNumber(num2);
	gjdChu(num1,num2,result);
	for(int i=result[0]; i>0; i--) {
		if(result[i]!=0)
			cout<0; i--) {
		cout<

输出结果：

24.png

3. 总结

本文讲解了高精度相加、相减、相乘、相除操作。面对大数值运算时，除了要有好的算法，还需要有低层硬件的支持。在实际进行超高精度数值运算时，可能需要集群环境下并发运算能力的支持。

  • 相关阅读:
    鸿鹄工程项目管理系统em Spring Cloud+Spring Boot+前后端分离构建工程项目管理系统
    【3. MySQL日志】
    MYSQL中的锁
    数据准备之日志采集发展历程
    【云原生】设备云之FlexManager历史数据的运用
    （附源码）springboot应用支撑平台和应用系统 毕业设计 984655
    浅析React Hook之useReducer
    S32K144 GPIO编程
    【办公类-21-04】20240227单个word按“段落数”拆分多个Word（三级育婴师操作参考题目 有段落文字和表格 1拆13份）
    hive on spark 记录
  • 原文地址：https://blog.csdn.net/y6123236/article/details/128034681