【算法】高精度乘法

前言

最近在参加某个比赛的时候遇到了这个问题，用字符串表示时，长度能达到15，所以针对大数乘法写一篇文章。

高精度 * 低精度

在这种场景下，一般都是给定一个无法用int或long long 存储的数，再给定一个能用int或long long存储的数，让你求他们相乘的结果。

算法思路：
1、首先，我们将无法存储的数以字符串的形式存储，定义为s ；将能被存储的数字定义为d
2、开辟一个数组a，用来保存s的每个位上的数字
3、第一次遍历数组a，将每个数字都乘以d
4、第二次遍历数组a，进位、保留10以内的数字
4.1、如果能被10整除，将a[i]/10 加到a[i+1]上，同时 a[i] %= 10
4.2、不能则结束这个位置的进位

细节：
1、结果a的长度len一开始被定义为s的元素个数，但随着不断进位，如果满足4.1的条件，则说明一定进到了下一位，如果此时恰好是a的最后一个位置，则要让len++再次循环一次

2、读入字符串的时候我们是正着读取的，但是处理时要reverse逆置，方便操作；输出结果时要倒着输出。

代码

//高精度 * 低精度
void HighLow(string s, long long d) {

	vector<long long> a(N, 0);
	reverse(s.begin(), s.end());
	int len = s.size();
	for (int i = 0; i < len; i++) {
		a[i + 1] = s[i] - '0';
	}

	for (int j = 1; j <= len; j++) {
		a[j] *= d;
	}

	for (int j = 1; j <= len; j++) {
		if (a[j] >= 10) {
			a[j + 1] += a[j] / 10;
			a[j] %= 10;
			if (j == len) len++;
		}
	}

	for (int i = len; i >= 1; i--) {
		cout << a[i];
	}
	cout << endl;
}

高精度 * 高精度

在这种场景下，一般都是给定两个无法用int或long long 存储的数，让你求他们相乘的结果。

我们先来回顾一下，当我们进行乘法运算时的步骤：

在这里插入图片描述

算法思路；
1、首先将两个数字以字符串的格式存取，定义为a、b
2、遍历a、b，将他们每个位上的数字存储在A、B两个数组上
3、由上面我们对乘法公式的推导，使用双重循环遍历A、B的每一个数字即C[i+j] += A[i]*B[j];
4、再遍历C数组，和上面处理进位和保留的方式一致。

细节：
注意到结果数组C我们定义的大小是lenc = lena + lenb ，例如999 * 999 是一定小于等于6位的，但我们无法确定是否一定是六位，比如20*20只有三位，所以在最后处理结果的时候，要从后去掉0直到遇到第一个非0的数字。

参考代码

void HighHigh(string a, string b) {
	reverse(a.begin(),a.end());
	reverse(b.begin(),b.end());

	int lena = a.size();
	int lenb = b.size();
	int lenc = lena + lenb;
	vector<int> A(lena+1,0), B(lenb+1,0) , C(lenc,0);
	for (int i = 0; i < lena; i++) {
		A[i] = a[i] - '0';
	}
	for (int i = 0; i < lenb; i++) {
		B[i] = b[i] - '0';
	}

	for (int i = 0; i < lena; i++) {
		for (int j = 0; j < lenb;j++) {
			C[i + j] += A[i] * B[j];
		}
	}

	for (int i = 0; i < lenc; i++) {
		if (C[i] >= 10) {
			C[i + 1] += C[i] / 10;
			C[i] %= 10;
			if (i == lenc - 1) {
				lenc++;
			}
		}
	}

	int pos = lenc - 1;
	while (C[pos] == 0) pos--;
	while (pos >= 0) {
		cout << C[pos];
		pos--;
	}
	cout << endl;

}