高精度算法

本篇将介绍高精度算法

---

简介

高精度计算运用算法结构，来支持更大区间的数字运算。
基本思想是通过模拟各位计算，用来作为模拟算法的练习较为不错。

存储&输入输出

一般的数字，我们使用int/long/long long进行存储，但是大区间的数字未必存的下。针对这个问题，我们使用字符串读取高精度数字。

在计算的时候，为了模拟我们小学的时候学的竖式运算，我们会将每一位分开存储，且从小到大计算。所以在数组中下标小的存放的是数字的 最低位。而在字符串中默认使用左高右低的十进制写法，当我们存储到数组中的时候，就需要「反转存储」

注：作者后续都会使用vector向量的写法，实际上使用任意一维数组都可以
由此易得高精度输入和输出的代码：

void read(vector<int> *a) {
	string s;
	cin >> s;
	for(int i = s.size() - 1;i >= 0;i--) a.push_back(s[i]); //反转存储
}

void print(vector<int> a) {
    while(a.size() && a.back() == 0) a.pop_back(); //删除所有的前导零
	for(int i = a.size() - 1;i >= 0;i--) cout << a[i]; //逆序输出
}

四则运算

四则运算的难度不同，我们将从易到难进行讲解

加法

高精度加法即为对竖式运算的模拟

从最低位开始，将两个同样位置的数字相加，并判断是否大于10，如果大于则需要考虑进位。
进位则将更高一位的结果上加1，当前位结果减10。

vector<int> add(vector<int> A, vector<int> B) {
	if (A.size() < B.size()) return add(B,A);
	vector<int> C;
	int t = 0;
	for(int i = 0;i < A.size();i++){
		t += A[i];
		if(i < B.size()) t += B[i]; // 判断B是否够长 
		C.push_back(t % 10);
		t /= 10;
	}
	if (t) C.push_back(t);
	return C;
}

减法

减法依旧是对竖式减法的模拟

从最低位开始，将两个同样位置的数字相减，遇到负数则考虑借位。
借位则需要向上一位借1，当前位加10。
和加法不同的是，我们这里需要判断减数和被减数的大小，来选择是否输出负号

bool cmp(vector<int> A,vector<int> B){ //比较两个高精度数字的大小
	if (A.size() != B.size()) return A.size() < B.size();
	for (int i = A.size() - 1;i >= 0;i++){
		if (A[i] != B[i]) return A[i] < B[i];
	}
	return false;
}

vector<int> sub(vector<int> A, vector<int> B) {
	if (cmp(A,B)) {
		cout << '-';
		return sub(B,A);
    }
	vector <int> C;
    int t = 0;
    for(int i = 0; i < A.size(); i++){
        t = A[i] - t;
        if(i < B.size()) t -= B[i];
        C.push_back((t + 10) % 10); // t+10是为了避免t<0 
        if(t < 0) t = 1; // 借位 
        else t = 0; // 不借位 
    }
    while(C.size() > 1 && C.back() == 0) C.pop_back();  //去掉前导0
    return C;
}

乘法

乘法的竖式运算实际上是计算了每一位相乘的和，例如：$47\times32=7\times2+40\times2+7\times30+40\times30$
于是我们可以将两个高精度数字的每一位数码相乘，并加到他们数位之和的位置

vector <int> mul(vector <int> &A, vector <int> &B) {
    vector <int> C(A.size() + B.size(), 0); //初始化答案向量大小
    for (int i = 0; i < A.size(); i ++) {
	    for (int j = 0; j < B.size(); j ++){
		    C[i + j] += A[i] * B[j];
		    C[i + j + 1] += C[i + j] / 10;
		    C[i + j] %= 10;
		}
    }
    while (C.size() > 1 && C.back() == 0) C.pop_back(); //删去前导零
    return C;
}

除法

关于竖式除法实际上可以看作数个减法的过程。
$\because324=12\times20+12\times7$
$\therefore324\div12=20+7=27$
当除数大于被除数时，被除数就是余数。当被除数大于除数时，我们可以从 $l_{被除数}-l_{除数}$ 的位置开始依次从被除数中减去除数，减去的个数就是对应位数的答案，这里需要使用前面提到的高精度减法的模板

bool cmp(vector<int> A, vector<int> B) { //比较两个高精度数字的大小
    if (A.size() != B.size()) return A.size() > B.size();
    for (int i = A.size() - 1; i >= 0; i--) {
        if (A[i] != B[i]) return A[i] > B[i];
    }
    return true; 
}

vector<int> sub(vector<int> A, vector<int> B) { //减法模板，具体看上文
    vector<int> C;
    int t = 0;
    for (int i = 0; i < A.size(); i++) {
        t = A[i] - t;
        if (i < B.size()) t -= B[i];
        C.push_back((t + 10) % 10);
        if (t < 0) t = 1;
        else t = 0;
    }
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

vector<int> div(vector<int> A, vector<int> B, vector<int> &R) {
    //A=被减数 B=减数 R=余数
    vector<int> C; //初始化答案向量
    R.clear();
    R.push_back(0);
	// 从最高位开始，逐位试商
    for (int i = A.size() - 1; i >= 0; i--) {
        R.insert(R.begin(), A[i]);
        while (R.size() > 1 && R.back() == 0) R.pop_back(); // 去前导0
        int q = 0;
        while (cmp(R, B)) {
            R = sub(R, B);
            q++;
        }
        C.push_back(q);
    }
    reverse(C.begin(), C.end()); // 答案现在是高位在前，翻转成低位在前
    while (C.size() > 1 && C.back() == 0) C.pop_back(); // 去前导0
    return C;
}