数值处理-高精度

在现实中的计算问题：

1.天文学中的距离计算

在天文学领域，科学家们常常需要计算星系之间的距离。例如，测量地球与遥远星系仙女座星系的距离。仙女座星系距离地球约 254 万光年，1 光年约等于(9.461×10^12)千米。那么地球与仙女座星系的距离大约是(2540000×9.461×10^12)千米。这个数值非常巨大，使用常规的数值类型（如 double ）很难精确表示。double 虽然能表示很大的数，但在精度上会有所损失，特别是对于这种需要精确计算的天文距离。

2.密码学中的大整数运算

在现代密码学中，RSA 加密算法是一种广泛使用的非对称加密算法。RSA 算法的核心运算涉及到非常大的整数的乘法和取模运算。例如，生成 RSA 密钥对时，需要选择两个大质数p和q，这两个质数通常有几百位甚至上千位。计算(n = p×q)时，这个乘积n就是一个极大的整数。如果使用常规数据类型，根本无法容纳这么大的数值，更无法进行后续基于这个大整数的加密和解密运算。

高精度算法可以通过模拟多位数字的运算，准确地表示和计算这些巨大数值，确保数据的准确性。

一、什么是高精度计算

高精度计算主要用于需要极高精度和处理大数字的场景，如科学研究、金融计算、密码学、天文学等领域。它是一种能够处理超出普通数据类型（如32位整数、64位浮点数等）表示范围的数值计算方法。

核心思想：将大数分解为计算机可处理的基本单元，使用数组或其他数据结构来存储和操作，通过模拟人工计算的逻辑（如逐位操作、进位/借位处理）实现高精度运算。

二、高精度计算过程

1.数据存储

数组存储：

以整数为例，将数字的每一位存储在数组的一个元素中。例如，对于整数 12345，可以用数组 [5, 4, 3, 2, 1] 表示，低位数字放在数组的低索引位置，高位数字放在高索引位置（便于从左到右遍历数字，方便从低位开始计算）。

字符串存储：

例如，数字 1234567890123456 可以存储为字符串 "1234567890123456" 。

2.运算实现

高精度算法通过模拟手工计算的方法来实现基本的算术运算，包括加法、减法、乘法和除法。

加法：

逐位相加：从最低位开始，逐位相加。
处理进位：如果某一位的和大于等于10，则向高位进位。
结果存储：将每一位的结果存储在结果数组或字符串中。

减法：

逐位相减：从最低位开始，逐位相减。
处理借位：如果某一位的被减数小于减数，则从高位借位。
结果存储：将每一位的结果存储在结果数组或字符串中。

乘法：

长乘法：模拟手工乘法的竖式计算过程，逐位相乘并处理进位。
优化算法：对于非常大的数字，可以使用更高效的算法，如Karatsuba（卡拉次巴）算法或Toom-Cook算法。

除法：

长除法：模拟手工除法的竖式计算过程，逐位相除并处理余数。
优化算法：对于非常大的数字，可以使用更高效的算法，如牛顿迭代法。

三、高精度算法的实现

3.1 高精度加法

两个大整数 987654321012345 和 666677778888 相加，使用高精度加法的实现过程如下：

1.准备数据：（以数组为例）

将两个大数分别反向存于整数数组a和b，左低右高

数组a:

5	4	3	2	1	0	1	2	3	4	5	6	7	8	9

数组b:

8	8	8	8	7	7	7	7	6	6	6	6

2.计算过程：逐位相加并处理进位

创建一个结果数组 c 并初始化为0，数组c的长度为a,b数组最大长度加1，max(len(a),len(b))+1。

创建一个保存进位的临时变量 t 。

逐位相加并处理进位：


变量t	0	1	1	1	1	0	0	0	0	0	1	1	1	0	0	0
a	5	4	3	2	1	0	1	2	3	4	5	6	7	8	9
b	8	8	8	8	7	7	7	7	6	6	6	6
c	3	3	2	1	9	7	8	9	9	0	3	3	8	8	9	0

3.输出结果：

去掉数组c高位的0，反向输出数组c: 988330998791233。

示例代码（用数组实现）：


1
#include<iostream>
2
#include<string>
3
using namespace std;
4
int a[240],b[240],c[250];
5
int main() {
6
    int len,len1,len2,t=0;
7
    string s1,s2;
8
    cin>>s1>>s2;
9
    len1=s1.size(),len2=s2.size();
10
    //1. 转存字符串数字到整型数组a,b
11
    //转存时把数字反转，便于从数组左边加到右边（便于末位进位）
12
    for(int i=len1-1; i>=0; i--)
13
        a[len1-1-i]=s1[i]-'0';
14
    for(int i=len2-1; i>=0; i--)
15
        b[len2-1-i]=s2[i]-'0';
16
    //2. 获取两个字符串的最大长度，按最大长度相加两个大数
17
    len=len1>len2?len1:len2;
18
    for(int i=0; i<len; i++){
19
        t+=a[i]+b[i];   //两数的和与进位相加，存入t
20
        c[i]=t%10;  //把去掉进位后的数字存入c
21
        t/=10;  //保留进位
22
    }
23
    //3. 检查末位进位情况
24
    if(t)
25
        c[len++]=t;
26
    //4. 倒序输出结果
27
    for(int i=len-1;i>=0;i--)
28
        cout<<c[i];
29
    return 0;
30
}

3.2 高精度减法

两个大整数 987654321012345 和 666677778888 相减，使用高精度减法的实现过程如下：

1.准备数据：（以字符串为例）

将两个大数分别存入字符串a和b，两个数相减后位数不会增加，所以这里不用反转数字。

a=“987654321012345” , b=“666677778888”

声明并初始化一个结果字符串 s=“” ;

2.确保被减数大于减数，即 a-b 时 a 要大于 b，如果 b>a 就交换 a 和 b。

3.从后向前逐位相减，并循环处理借位。把得数添加到结果数组 s 中。

4.删除结果中的前导 0 ，并输出。

示例代码（用字符串实现）：


x
1
#include<iostream>
2
#include<string>
3
using namespace std;
4
int main() {
5
    string a,b,s="";
6
    cin>>a>>b;
7
    //确保a>b,否则先输出负号且交换a和b;
8
    if (a.size()<b.size()||(a.size()==b.size()&&a<b)) {
9
        cout<<"-";
10
        swap(a,b);
11
    }
12
    if(a==b) {//两个数相等就直接输出0且结束程序
13
        cout<<0;
14
        return 0;
15
    }
16
    int lena=a.size()-1,lenb=b.size()-1;
17
    //已经是a>b的状态
18
    while(lena>=0&&lenb>=0) {
19
        int ai=a[lena]-'0',bi=b[lenb]-'0',si;
20
        if(ai>=bi)si=ai-bi;//如果够减就直接减
21

22
        else { //否则就借位,如果左位是'0'，就继续向左借。
23
            int k=1;
24
            while(a[lena-k]=='0') { //循环借位
25
                a[lena-k]='9';//如果左边位是0，就直接变成9
26
                k++;
27
            }
28
            a[lena-k]--;//直到非0位，停止借位并减1
29
            si=ai+10-bi;
30
        }
31
        s=to_string(si)+s;//把结果写入s
32
        lena--;//右指针向左移
33
        lenb--;
34
    }
35
    if(lena>0)s=a.substr(0,lena+1)+s;//把被减数剩下的写入s
36
    //删除结果中的前导0
37
    while(s[0]=='0') {
38
        s.erase(0,1);
39
    }
40
    cout<<s;
41
    return 0;
42
}

3.3 高精度乘法

两个大整数 987654321012345 和 666677778888 相减，使用高精度减法的实现过程如下：

1.准备数据

创建并初始化一个结果数组，大小为两个乘数的长度之和。

2.逐位相乘

使用嵌套循环，从最低位开始逐位相乘。对于每个乘积，将其加到结果数组的相应位置。

3.处理进位

在逐位相乘的过程中，如果某一位的乘积加上之前的进位大于等于10，则需要将进位加到下一位。这一步也可以在逐位相乘完成之后单独处理。

4.去掉前导零并输出。

计算过程示例：

示例代码：


xxxxxxxxxx
31
1
#include<iostream>
2
#include<string>
3
#include<algorithm>
4
using namespace std;
5
int main() {
6
    string a,b;
7
    int ans[500]= {0};
8
    cin>>a>>b;
9
    if(a=="0"||b=="0") {
10
        cout<<0;
11
        return 0;
12
    }
13
    int la=a.size(),lb=b.size();
14
//1. 逐位相乘，按乘法竖式相加到ans数组
15
    for(int i=la-1; i>=0; i--) {
16
        for(int j=lb-1; j>=0; j--) {
17
            //ans数组从后向前存储结果，高位在左，低位在右
18
            ans[i+j+1]+=(a[i]-'0')*(b[j]-'0');
19
            //ans[i+j+1]:+1是为了留出一个空位给最高位进位
20
        }
21
    }
22
//2. 处理进位，从右向左进位
23
    for(int i=la+lb-1; i>=0; i--) {
24
        ans[i-1]+=ans[i]/10;
25
        ans[i]%=10;
26
    }
27
//3. 输出
28
    if(ans[0]!=0)cout<<ans[0];//最高位按是否有进位输出
29
    for(int i=1; i<=la+lb-1; i++)cout<<ans[i];
30
    return 0;
31
}

3.4 高精度除法

3.4.1 高精除以低精（按位相除法）

以123456789/45为例的处理过程：

初始化：设被除数为数组 A[]={1,2,3,4,5,6,7,8,9}表示123456789，除数为 b=45，结果数组 C[]，余数 r = 0。
从高位到低位计算（逐位计算）：
- 对每一位i（从最高位开始）：
  - 当前被除数部分：r = r * 10 + A[i]
  - 计算商：C[i] = r / b
  - 更新余数：r = r % b
去除前导零
输出结果

参考示例：


xxxxxxxxxx
39
1
#include <iostream>
2
#include <cstring>
3
using namespace std;
4
const int MAXN = 1000; // 最大位数限制
5
int main() {
6
    char a[MAXN]; // 存储原始数字字符串
7
    int b;        // 除数
8
    cin >> a >> b; // 输入被除数和除数
9
    // 将字符串转为数字数组（自然顺序，A[0]是最高位）
10
    int A[MAXN], lenA = strlen(a);
11
    for (int i = 0; i < lenA; i++) {
12
        A[i] = a[i] - '0'; // 字符转数字
13
    }
14
    int r = 0; // 余数初始化
15
    int C[MAXN]; // 商数组
16
    // 核心计算：从左到右逐位处理
17
    for (int i = 0; i < lenA; i++) {
18
        r = r * 10 + A[i]; // 当前被除数部分
19
        C[i] = r / b;      // 当前位的商
20
        r %= b;            // 更新余数
21
    }
22
    // 去除前导零（找到第一个非零位置）
23
    int start = 0;
24
    while (start < lenA && C[start] == 0) {
25
        start++;
26
    }
27
    // 输出商（若全为零则输出0）
28
    if (start == lenA) {
29
        cout << "0";
30
    } else {
31
        for (int i = start; i < lenA; i++) {
32
            cout << C[i];
33
        }
34
    }
35
    // 输出余数
36
    cout << endl << r << endl;
37

38
    return 0;
39
}