博客

高精度乘法

其他高精度算法如下：


高精度加法 【c++实现】



高精度减法【c++实现】



高精度除法【c++实现】


————————————————————————

想必大家已经学完了高精度加法与减法了！那么让我们再来一起学习高精度乘法吧~

如果没学过不要紧，看这里——>

高精度加法【c++实现】

与

高精度减法【c++实现】

简单的高精度乘低精度：

顾名思义就是一个大整数乘以一个int型的数字

举个例子：32145 * 16 =514320

计算过程如同我们的竖式计算，可以手动计算一下，或者请看下方视频。

代码实现时，设 a 为大整数即用数组存储的数字，b 为一个int型的数字，结构存放在数组 ans 里。


需要注意的一点是 a[ i ] (0< i < len_a_max) 乘 b 不能超过 int 的上限！！！


可以很容易知道 ans[ i ] = a[ i ] * b + carry; 因此简单的把 a 遍历一遍就能得到结果，注意最后的进位不能忽略，因此循环条件就不能单纯的是按照 a 的长度来，还要再加上对进位是否为 0 的判断。

#include <iostream>
using namespace std;
int main(){
	//计算 a * b = ans , 其中 a 为大整数 , b 为 int 型数字
	int a[520]={0},ans[521]={0};
	
	int b,i,j,len_a,carry=0; //len_a 为数字 a 的长度 , carry为进位, 记得一定要初始化 carry = 0 
	string a_s;
	
	cin>>a_s>>b; //接受字符串型 a_s , 和 int 型数字 b 
	
	len_a=a_s.length(); //计算 大整数 a 的长度 , 使用string类里的函数 length() 
	
	for(i=0;i<len_a;i++){ //将string型的数字 a_s 转换为 int 型的数字倒序存储到 数组 a 里 
		a[i]=a_s[len_a-1-i]-'0';
	}
	
	for(i=0;i<len_a||carry!=0;i++){ //核心计算过程 ,注意最后的进位 
		ans[i]=a[i]*b+carry;  
		carry=ans[i]/10;
		ans[i]%=10;
	}
	
	int len=i; // 因为计算完后 a[i] 为数组的最后一个数字, 那么 i 即为 ans 的长度 
	
	while(ans[len]==0&&len>0) len--; //去除前缀无用的 0 
	
	for(i=len;i>=0;i--){ // 倒序输出最终的答案 
		cout<<ans[i];
	}
} 

进阶的高精度乘高精度:

这里也就是两个大整数相乘的，仍然举上面的例子：32145 * 16 =514320，具体计算过程且看下方视频，或者你也可以手动计算一下竖式。

这里我们先姑且称 32145 为被乘数，16为乘数。经过模拟可以知道，实际上就是用乘数的每一位依次去乘被乘数，那么这样子就变成了高精度乘低精度的做法，相信你已经学会了！只不过每次 ans 开始相加的地方不同（相信你一定注意到了，乘数的第一位乘被乘数时，ans从ans[0] 开始，第二位乘被乘数时，ans从ans[1] 开始），这个问题的解决请看代码。

代码实现如下：

#include <iostream>
using namespace std;
int main(){
	// 大整数 乘 大整数 是 大整数 乘 int 的进阶版 
	string a_s,b_s; //大整数 a 和 b 的字符串形式 
	int a[521]={0},b[521]={0},ans[521*2]={0}; //a, b, ans 的 int数组形式 
	
	int len_a,len_b,len,carry=0,i,j;
	//len_a 为 a 的长度, len_b为 b 的长度, len 为 ans 的长度, carry为进位 
	//切记carry要初始化为 0！！！ 
	
	cin>>a_s>>b_s; //接收两个整数 a, b 
	
	len_a=a_s.length();//分别计算长度 
	len_b=b_s.length();
	
	for(i=0;i<len_a;i++) a[i]=a_s[len_a-1-i]-'0';//分别转为 int 型并倒序存储 
	for(i=0;i<len_b;i++) b[i]=b_s[len_b-1-i]-'0';
	
	for(i=0;i<len_b;i++){ // 核心计算过程,外层循环为乘数, 内层循环为被乘数*int的高精乘低精算法 
		for(j=0;j<len_a||carry!=0;j++){
			ans[i+j]+=a[j]*b[i]+carry; //注意ans的下标为 i+j ! a和 b下标对应它的循环变量 
			carry=ans[i+j]/10;
			ans[i+j]%=10;
		}
	}
	
	len=i+j; //数组最后一个数字为 ans[i+j], 所以 i+j 即为ans长度 
	
	while(ans[len]==0&&len>0) len--; // 去除前缀无用的 0 
	
	for(i=len;i>=0;i--){ //倒序输出 
		cout<<ans[i];
	}
}

看到这里你已经学会了高精度乘法了，如果要熟练掌握还要多去实践哦！