acwing算法笔记-高精度运算

高精度运算

定义

首先我们来看一下什么是高精度运算，它又有哪些应用场景。

在一般的科学计算中，会经常算到小数点后几百位或者更多，当然也可能是几千亿几百亿的大数字。一般这类数字我们统称为高精度数，高精度算法是用计算机对于超大数据的一种模拟加，减，乘，除，乘方，阶乘，开方等运算。对于非常庞大的数字无法在计算机中正常存储，于是，将这个数字拆开，拆成一位一位的，或者是四位四位的存储到一个数组中， 用一个数组去表示一个数字，这样这个数字就被称为是高精度数。高精度算法就是能处理高精度数各种运算的算法，但又因其特殊性，故从普通数的算法中分离，自成一家。

通常我们遇到的问题涉及到的都是大整数运算，很少会遇到超高精度浮点数运算，所以我们在这里详细整理一下大整数运算的算法。


存储方式

首先我们回顾一下int, long long这些可以表示整数的数据类型的最大取值。

数据类型 最大值 位数（十进制）
int 2147483647 10
long long 9223372036854775807 19

这里很容易看出int类型变量无法存储超过10位的整数，即使是用long long也无法存储超过19位的整数。

那么大整数如何存储呢，对于大整数我们可以采取字符串去存储，但是这样虽然解决了存储问题，我们还是无法进行运算。所以在题目中我们常常用字符串作为大整数的输入输出。

那么为了进行运算，我们还可以采用数组去存放大整数，一个数组元素，存放大整数中的一位。其中存储的时候，我们采取逆序存储，即数值低位存储在数组低位。

为什么采取逆序存储

  1. 在手动实现加减法时，我们习惯从低位(个位)开始,(从后往前), 在处理数组时,我们习惯从第一个元素开始(从前往后)。
  2. 加法中会向高位进位，减法中会向高位借位。将数字逆序存储在数组中，对高位(前一位)数字的处理,只要处理数组的下一个元素 (下标+1)。
  3. 加法、乘法，其结果的高位长度不确定，会向前增加，例如加法中最高位再进位，但在数组的处理中，向末尾增加一个元素简单O(1)，向开头增加一个元素困难O(n)。
  4. 综上，在加减乘三种运算中，使用逆序存储，处理更简单。在同一个程序中，可能会同时运用加减乘除四种运算，因此虽然除法习惯从高位开始计算，但为了能统一处理，也选择逆序存储。

高精度加法

$A + B$
$len(A), len(B)<= 10^6 $

基本思想

模拟加法的实现过程

  1. 将两个数按个位对齐，从个位开始相加。
  2. A，B的当前数位相加，再加上上级进位t，得到和$sum = A[i] + B[i] + t[i-1]$ 。
  3. 根据sum，求出当前数位的结果和进位。

这里给出比较清晰的图示帮助理解

add1

参考代码

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
49
50
51
#include <iostream>
#include <vector>

using namespace std;


// 参数中，不加引用 &，则调用函数时会把向量 vector 整体复制一份
// 增加引用则不会，能提高速度 
vector<int> add(vector<int> &A, vector<int> &B)
{
    //函数只处理A > B的情况
    if (A.size() < B.size()) return add(B, A);

    // 用于存放结果
    vector<int> C;
    
    // t表示进位，个位没有上级进位，初始值为0 
    int t = 0;  
    for (int i = 0; i < A.size(); i ++ )
    {
        t += A[i];
        // B的长度<A的长度，所以防止越界
        if (i < B.size()) t += B[i];

        //当前位结果
        C.push_back(t % 10);

        //计算进位
        t /= 10;
    }

    //判断最高位是否有进位，其实可以写进for循环里，看个人习惯
    if (t) C.push_back(t);
    return C;
}

int main()
{
    string a, b;
    vector<int> A, B;
    cin >> 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');

    auto C = add(A, B);

    for (int i = C.size() - 1; i >= 0; i -- ) cout << C[i];
    cout << endl;

    return 0;
}

变量t既作为进位数，又作为加和的中间变量，t%10为每位的结果，t/10为进位数

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
//看到一份比较优雅的代码，然后自己写了一套自己的模板
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

string a, b;

string add (string &a, string &b) {
    int i = a.size() - 1, j = b.size() - 1, t = 0;
    string c;
    while (i >= 0 || j >= 0 || t) {
        if (i >= 0) t += a[i-- ] - '0';
        if (j >= 0) t += b[j-- ] - '0';
        c.push_back(t % 10 + '0');
        t /= 10;
    }
    
    reverse(c.begin(), c.end());
    return c;
}

int main () {
    ios::sync_with_stdio(false);
    cin >> a >> b;
    cout << add(a, b);
}

Reference

[1]. 高精度加法—y总思路介绍+手动模拟+详细代码及注释
[2]. 高精度加法（使用string，30行）

高精度减法

$A - B$
$len(A), len(B)<= 10^6 $

基本思想

模拟减法的实现过程

Step1
首先判断A，B大小关系
若 A > B ，则直接计算，若 A < B ，则计算 B - A ，在其结果前面加负号 -

Step2

  1. 将两个数按个位对齐，从个位开始相减
  2. A的当前数位先减去上级借位 ，再减去B对应数位，得到数值$t = A[i] - t[i-1] - B[i]$
  3. 通过t的符号，判断是否需要借位
  4. 求出该数位的结果和借位

这里给出比较清晰的图示帮助理解

sub1

参考代码

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
49
50
51
52
53
54
55
56
57
58
#include <iostream>
#include <vector>

using namespace std;

// 判断是否有 A >= B 
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;
    // t表示借位，个位没有上级借位，初始值为0 
    for (int i = 0, t = 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;
    }

    // 去掉前导 0
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

int main()
{
    string a, b;
    vector<int> A, B;
    cin >> 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;

    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
37
38
39
40
//自己的模板
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

string a, b;

bool cmp (string &a, string &b) {
    if (a.size() != b.size()) return a.size() > b.size();
    for (int i = 0; i < a.size(); i++ ) 
        if (a[i] != b[i]) return a[i] > b[i] ;
    return true;
}

string sub (string &a, string &b) {
    int i = a.size() - 1, j = b.size() - 1, t = 0;
    string c;
    while (i >= 0 || j >= 0) {
        if (i >= 0) t = a[i-- ] - '0' - t;
        if (j >= 0) t -= b[j-- ] - '0';
        c.push_back((t + 10) % 10 + '0');
        if (t < 0) t = 1;
        else t = 0;
    }
    
    while(c.size() > 1 && c.back() == '0') c.pop_back();
    reverse(c.begin(), c.end());
    
    return c;
}

int main () {
    ios::sync_with_stdio(false);
    cin >> a >> b;
    if (cmp(a, b)) cout << sub(a, b);
    else cout << '-' << sub(b, a);
    return 0;
}

变量t既作为借位数，也作为减法的中间变量。

为什么每位的结果是(t + 10) % 10
当每位的结果 $t = A[i] − t[i - 1] - B[i]> 0$, (t + 10)再% 10结果还是为t。
当 每位的结果$t = A [i] − t[i - 1] - B[i] < 0$ t + 10再% 10结果为借位后的个位部分。

为什么要去除前导零，最后几位减出来的0也同样被push_back进去了

Reference

[1]. Bug-Free
[2]. 二月 高精度减法-39ms-C++


高精度乘法

$A \times b$
$len(A)<= 10^6 $，$b < 10^6$

基本思想

  1. 将两个数按个位对齐
  2. 将乘数b看成一个整体，与被乘数A的当前数位相乘，再加上上级进位t，得到数值$t = A[i] \times b + t[i-1]$
  3. 求出该数位的结果和进位

div1

以上可以看出，乘法和加法十分类似

参考代码

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
#include <iostream>
#include <vector>

using namespace std;


vector<int> mul(vector<int> &A, int b)
{
    vector<int> C;

    int t = 0;
    // 循环有两个条件
    // 1. 大整数 A 各数位均要进行计算
    // 2. 大整数各数位计算完，但 t 仍有剩余，则还需要向前进位 ( t != 0 ) 
    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;
}


int main()
{
    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');

    auto C = mul(A, b);

    for (int i = C.size() - 1; i >= 0; i -- ) printf("%d", C[i]);

    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
//自己的模板
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

string a;
int b;

string mul (string &a, int b) {
    string c;
    int i = a.size() - 1, t = 0;
    while (i >= 0 || t) {
        if (i >= 0) t += (a[i-- ] - '0') * b;
        c.push_back(t % 10 + '0');
        t /= 10;
    }
    
    while (c.size() > 1 && c.back() == '0') c.pop_back();
    reverse(c.begin(), c.end());
    
    return c;
}


int main() {
    ios::sync_with_stdio(false);
    cin >> a >> b;
    cout << mul(a, b);
}

Reference

[1]. 高精度乘法-28ms-c++


高精度除法

$A \div b$
$len(A)<= 10^6 $，$b < 10^6$

基本思想

与加减乘不同，除法从高位开始算，但是为了和上述模板统一，因此也选择 逆序存储。实现过程与手动计算除法完全相同。

  1. 初始余数r = 0
  2. 上一位的余数$r \times 10 + A[i]$ 得到数值$r = r \times 10 + A[i] $
  3. 求出该数位的商和余数

div1

参考代码

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
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// A / b ，商是 C ，余数是 r
vector<int> div(vector<int> &A, int b, int &r)
{
    vector<int> C;
    r = 0;
    // 除法从高位向低位运算
    for (int i = A.size() - 1; i >= 0; i -- )
    {
        r = r * 10 + A[i];
        C.push_back(r / b);
        r %= b;
    }
    reverse(C.begin(), C.end());
    
    //去除前导0
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

int main()
{
    string a;
    vector<int> A;

    int B;
    cin >> a >> B;
    for (int i = a.size() - 1; i >= 0; i -- ) A.push_back(a[i] - '0');

    int r;
    auto C = div(A, B, r);

    for (int i = C.size() - 1; i >= 0; i -- ) cout << C[i];

    cout << endl << r << 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
//自己的模板很香
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

string a;
int b;

string div (string &a, int b, int &r) {
    string c;
    int i = 0;
    while (i < a.size()) {
        r = r * 10 + (a[i++ ] - '0');
        c.push_back(r / b + '0');
        r %= b;
    }
    
    reverse(c.begin(), c.end());
    while (c.size() > 1 && c.back() == '0') c.pop_back();
    reverse(c.begin(), c.end());
    
    return c;
}


int main() {
    ios::sync_with_stdio(false);
    cin >> a >> b;
    int r = 0;
    cout << div(a, b, r) << endl;
    cout << r;
}

Reference

[1]. 高精度除法-31ms-c++
[2]. Bug-Fre


总结

  1. 除了加法以外都要判断前导0
  2. 像加减乘我们都是从低位开始，所以倒序遍历，这样就可以低位开始遍历，而除法是从高位开始，所以我们不需要倒序遍历，直接就可以从高位开始遍历
  3. 进位，借位，前导0的删除涉及到了高位的增删，高位在左增删不方便，所以我们要把高位放在右边方便操作（加减乘倒序后高位在右，所以直接前导0的删除，而除法高位在左，所以翻转后删除前导0）
  4. 加减乘除都是模拟逐位计算的过程，其中加法和乘法有进位，所以计算的条件是数没有遍历完 + 进位非零，而减法除法没有进位，所以计算的条件是数没有遍历完

相关题目

算法 > AcWing
#算法 #高精度
acwing算法笔记-高精度运算
https://vendestine.com/big-integer
Author
Wenzhe Li
Posted on
March 25, 2022
Licensed under