YuriCode
0%

高精度算法

发表于 更新于 分类于
本文字数： 6.2k 阅读时长 ≈ 6 分钟

高精度算法

高精度算法主要用于处理比普通数据类型更大的数值。普通的数据类型（如 int, long long）无法满足对非常大的数进行计算时的需求。高精度算法通过模拟手工运算过程，逐位处理数字，保证了数值的准确性和有效性。

在高精度运算中，常见的操作包括加法、减法、乘法等，它们通常在字符串中以逐位的方式实现，以应对超过普通数据类型范围的数值。

辅助函数

去除字符串的前导零

1
2
3
4
5
6
void RE0 (string & str) {
    str.erase(0, str.find_first_not_of("0"));
    if (str.empty()) {
        str = "0";
    }
}

高精度加法

高精度加法通过逐位加法和进位处理来模拟实际的加法过程。下面是加法实现代码：

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
string add(string str1, string str2) {
    string str;
    int len1 = str1.size();
    int len2 = str2.size();
    
    // 对齐两个字符串长度
    if (len1 > len2) {
        for (int i = 0; i < len1 - len2; i++) {
            str2 = "0" + str2;
        }
    }
    if (len2 > len1) {
        for (int i = 0; i < len2 - len1; i++) {
            str1 = "0" + str1;
        }
    }
    
    int cf = 0; // 进位
    len1 = str1.size();
    for (int i = len1 - 1; i >= 0; i--) {
        int temp = str1[i] - '0' + str2[i] - '0' + cf;
        cf = temp / 10;  // 更新进位
        str = to_string(temp % 10) + str;  // 拼接结果
    }
    
    if (cf != 0) str = to_string(cf) + str;  // 如果有最终进位，加到结果前面
    return str;
}

高精度减法

高精度减法通过逐位减法和借位处理来模拟实际的减法过程。代码实现如下：

大数减小数

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
string sub(string str1, string str2) {
    string str;
    int len1 = str1.size();
    int len2 = str2.size();
    
    // 对齐两个字符串长度
    for (int i = 0; i < len1 - len2; i++) {
        str2 = "0" + str2;
    }
    
    int br = 0; // 借位
    for (int i = len1 - 1; i >= 0; i--) {
        int temp = (str1[i] - '0') - (str2[i] - '0') - br;
        if (temp < 0) {
            temp += 10;  // 处理借位
            br = 1;
        } else {
            br = 0;
        } 
        str = to_string(temp) + str;  // 拼接结果
    }
    
    RE0(str);  // 去除多余的前导零
    return str;
}

任意两数

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
bool compare(string str1, string str2) {
	int len1 = str1.size();
	int len2 = str2.size();	
	if (len1 != len2) return len1 < len2;
	else return str1 < str2;	
}

string sub(string str1, string str2) {	
	string str;
	string flag;
	if (compare(str1, str2)) {
		swap(str1, str2);
		flag = "-";
	}
	int len1 = str1.size();
	int len2 = str2.size();	
	for (int i = 0; i < len1 - len2; i++) {
		str2 = "0" + str2;	
	}	
	int br = 0;
	len1 = str1.size();
	for (int i = len1 - 1; i >= 0; i--) {
		int temp = (str1[i] - '0') - (str2[i] - '0') - br;
		if (temp < 0) {
			temp += 10;
			br = 1;
		} else {
			br = 0;
		}
		str = to_string(temp % 10) + str;
	}
	RE0(str); 
	str = flag + str;
 	return str;
}

高精度乘法

高精度乘法通过逐位乘法和进位处理来模拟实际的乘法过程。实现代码如下：

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
string mul(string str1, string str2) {
    string str;
    int len1 = str1.size();
    int len2 = str2.size();
    string tempstr;
    
    for (int i = len2 - 1; i >= 0; i--) {
        int temp = str2[i] - '0';
        tempstr = "";
        int t = 0;
        int cf = 0;
        
        if (temp != 0) {
            // 添加对应的零
            for (int j = 1; j <= len2 - 1 - i; j++) {
                tempstr = tempstr + "0";
            }
            
            // 乘法运算
            for (int j = len1 - 1; j >= 0; j--) {
                t = (temp * (str1[j] - '0') + cf) % 10;
                cf = (temp * (str1[j] - '0') + cf) / 10;
                tempstr = to_string(t) + tempstr;
            }
            
            if (cf != 0) tempstr = to_string(cf) + tempstr;  // 添加进位
        }
        
        // 累加到结果
        str = add(str, tempstr);  
    }
    
    RE0(str);  // 去除前导零
    return str;
}

y总版本

高精度加法

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
#include <bits/stdc++.h>
#define int long long 
using namespace std;

const int N = 1e6 + 10;

vector<int> add(vector<int> &A, vector<int> &B)
{
	vector<int> C;
	int t = 0;
	for (int i = 0; i < A.size() || i < B.size(); i++) {
		if (i < A.size()) t += A[i];
		if (i < B.size()) t += B[i];
		C.push_back(t % 10);
		t /= 10;
	}
	if (t) C.push_back(t);
	return C;
}

signed main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	string a, b;
	cin >> a >> b;
	vector<int> A, B;
	for (int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');
	for (int i = b.size() - 1; i >= 0; i--) B.push_back(b[i] - '0');
	
	vector<int> C = add(A, B);
	for (int i = C.size() - 1; i >= 0; i--) {
		cout << C[i];
	}
	cout << endl;
	return 0;
}

高精度减法

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
#include <bits/stdc++.h>
#define int long long 
using namespace std;

const int N = 1e6 + 10;

bool cmp(string &a, string &b)
{
	if (a.size() != b.size()) return a.size() > b.size();
	else return a > b;
	return 1;
}

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;
}

signed main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	string a, b;
	cin >> a >> b;
	vector<int> A, B, C;
	for (int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');
	for (int i = b.size() - 1; i >= 0; i--) B.push_back(b[i] - '0');
	if (cmp(a, b)) {
		C = sub(A, B);
	} else {
		C = sub(B, A);
		cout << "-";
	}
	for (int i = C.size() - 1; i >= 0; i--) {
		cout << C[i];
	}
	cout << endl;
	return 0;
}

高精度乘法（高精度 * 低精度）

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
#include <bits/stdc++.h>
#define int long long 
using namespace std;

const int N = 1e6 + 10;

vector<int> mul(vector<int> &A, int &b)
{
	vector<int> C;
	int t = 0;
	//这里 || t 是因为进位的结果还没有存储
	for (int i = 0; i < A.size() || t; i++) {
		if (i < A.size()) t += A[i] * b;
		C.push_back(t % 10);
		t /= 10;
	}
	while (C.size() > 1 && C.back() == 0) C.pop_back();
	return C;
}

signed main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	string a;
	int b;
	cin >> a >> b;
	vector<int> A;
	for (int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');
	
	vector<int> C = mul(A, b);
	for (int i = C.size() - 1; i >= 0; i--) {
		cout << C[i];
	}
	cout << endl;
	return 0;
}

高精度除法（高精度 / 低精度）

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
#include <bits/stdc++.h>
#define int long long 
using namespace std;

pair<vector<int>, int> div(vector<int> &A, int &b)
{
	vector<int> C;
	int r = 0;
	//注意这里为了和其他高精度算法统一
	//所以从后面往前面遍历
	//把A倒着存进去然后再倒着输出来，实际上就相当于正着输
	for (int i = A.size() - 1; i >= 0; i--) {
		r = r * 10 + A[i];
		C.push_back(r / b);
		r %= b;
	}
	//所以这里最终的结果0在前面，而其他算法0都在后面
	//把结果倒过来是为了删除前导0
	reverse(C.begin(), C.end());
	while (C.size() > 1 && C.back() == 0) C.pop_back();
	return {C, r};
}

signed main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	string a;
	int b;
	cin >> a >> b;
	vector<int> A;
	for (int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');
    pair<vector<int>, int> ans;
    ans = div(A, b);
    vector<int> C = ans.first;
    int r = ans.second;
    for (int i = C.size() - 1; i >= 0; i--) cout << C[i]; cout << endl;
    cout << r << endl;
}