高精度算法

为什么要有高精度运算？因此计算机内部我们常用的数据类型能表示的范围都是有限的，比如 int 为 4 个字节，也就是 32 位，最大也只能表示 $2^{31}-1$ 这么大的数（大概 9 位十进制能表示的数字大小）。

而 C++ 中的 long long 类型，最大也只能表示 $2^{63} - 1$ 这么大（大概 18 位十进制能表示的数字大小）。

如果要对超过这个范围的大数进行运算怎么办呢？这时就需要用到高精度运算。

高精度运算，就是指参与运算的数字（无论是加法、减数还是乘数 ......），其大小远远超过 C++ 中标准数据类型所能表示的范围的运算。

比如 20、50、100 位这样的大数字，连 long long 都无法存储，我们通常称这样的数为大数（bignum）

高精度算法通常使用数组或字符来存储数值，并逐位进行操作来实现。以数组实现为例，在计算时把数字存储到数组中，再按我们小学学过的坚式计算方法，一位一位地进行加、减、乘、除等运算，该进位进位，计算完后再把结果数组中的各个位拼在一起就得到最终运算的结果。

为了更好的理解为什么有高精度运算，了解 C++ 中基本数据类型的范围是很有必要的，建议大家再去讲解变量的章节看看不同数据类型能够表示的数据范围。

高精度运算常见的形式有下面几种，下面都会谈到：

计算 $2^N$ ，其中 N 超过 64
计算 $A + B$ ，其中 $A$ 与 $B$ 均为「大数」
计算 $A - B$ ，其中 $A$ 与 $B$ 均为「大数」
计算 $A \times b$ ，其中 $A$ 为「大数」， $b$ 为普通的可以用 int 表示的数
计算 $A \div b$ ，其中 $A$ 为「大数」， $b$ 为普通的可以用 int 表示的数，且 b 不等于 0

高精度运算基本思路

将要进行运算以字符串类型读入
将读入的字符串拆分开，转换为数字并逆序存储入数组
利用数组按照运算法则从左至右依次计算，并将结果存入结果数组
按要求逆序输出结果数组的数字

高精度加法 A+B

例如，求两个大数的数字之和，大数超过 20 位。

例如：

65476547645485485486859675132
76528989565454376596796475347

超过 20 位的大数相加，就是典型的高精度加法 $A+B$ 问题，我们一起来看看如何求解。

方法一：数组实现

我们在数学中用到的竖式加法，是按从右到左（也就是低位到高位）来计算的，进位也是从左向右进位。而数组的下标是从左至右依次增长的，为了方便计算，我们将字符串拆分后逆序存入加数数组，从而利用数组来实现从左向右计算，进位也是从左向右进位。

实现代码

#include <bits/stdc++.h>
using namespace std;

const int N = 250;
int a[N], b[N], c[N];

int main() {
  string s1, s2; // 按字符串读入两个加数
  cin >> s1 >> s2;
  
  // 将 s1 逆序，转换为数字后存入数组 a
  for (int i = s1.size() - 1, j = 0; i >= 0; i--, j++) {
    a[j] = s1[i] - '0';
  }
  
  // 将 s2 逆序，轮换为数字后存入数组 b
  for (int i = s2.size() - 1, j = 0; i >= 0; i--, j++) {
    b[j] = s2[i] - '0';
  }
  
  // 以位数较大的加数为准进行加法
  int len = max(s1.size(), s2.size());

  // 按位进行加法运算
  int t = 0; // t 代表进位
  for (int i = 0; i < len; i++) {
    t = t + a[i] + b[i];
    c[i] = t % 10; // 当前位的值
    t /= 10; // 每次的进位
  }
  
  if (t > 0) c[len++] = t; // 如果最后还有进位，新增一位
  
  // 最后逆序输出计算结果
  for (int i = len - 1; i >= 0; i--) {
    cout << c[i];
  }
  
  return 0;
}

方法二：字符串实现

充分利用了字符与字符串的特点，包括：

字符与数字之间的相互转换
字符串拼接顺序会造成结果刚好逆序

另外，利用 while 循环，解决了两个字符串长度不一致相加的问题，我们在方法一中，是直接以更长的字符串为准来计算的，而方法二中，巧妙的避开了这一点。

#include <bits/stdc++.h>
using namespace std;

string s1, s2;
int main() {
  cin >> s1 >> s2;
  
  int i = s1.size() - 1;
  int j = s2.size() - 1;
  
  string rlt = "";
  int carry = 0;
  char c;
  
  while (i >= 0 || j >= 0 || carry > 0) {
    int sum = carry;
    if (i >= 0) sum = sum + s1[i--] - '0';
    if (j >= 0) sum = sum + s2[j--] - '0';
    c = sum % 10 + '0';
    rlt = c + rlt;
    carry = sum / 10;
  }
  
  cout << rlt;
  return 0;
}

高精度减法 A-B

这里我们考虑的是高精度 A 减去高精度 B。

例如，求两个不超过 240 位的数字之差。

例如：

76528989565454376596796475347
65476547645485485486859675132

高精度减法的原理完全模仿我们手算减法的竖式过程：

对齐： 将两个数字的个位对齐。
逐位计算： 从个位开始，从右往左，依次计算对应位的差。
借位： 如果当前位的被减数小于减数，就需要向高一位“借位”。从高一位借来的 1 相当于当前位的 10。

实现步骤

在真正实现的过程中，还有一些细节需要注意，假设我们要计算 $A-B$ ，其中 $A$ 和 $B$ 都是用数组存储的高精度数字，可按以下步骤来执行：

输入两个数字：按字符串读入两个非负整数，并将两个非负整数转换为vector<int>。
确定大小： 首先要判断 A 和 B 哪个更大，确保大数在前。
- 如果 A > B，结果是正数。
- 如果 A < B，结果是负数，我们可以计算 B - A，然后给结果加上负号。
- 如果 A = B，结果是 0。
- 为了简化，我们通常只实现 A >= B 的情况，如果 A < B，就交换 A 和 B，计算 B - A，最后输出时加负号。
逐位相减： 从最低位（数组下标 0）开始，遍历到最高位。该借位就借位。
去除前导零： 计算完成后，结果数组的最高位可能出现 0（比如 123 - 120 = 003）。需要从最高位开始，去除连续的前导零，直到遇到第一个非零数字或只剩下一位。

注意：为了降低复杂度，我们这里只考虑两个非负整数相减的情况；用 vector 替代了 array，用法与数组差不多，但更灵活一些

代码实现

#include <bits/stdc++.h>
using namespace std;

// 用于比较两个高精度数字的大小
bool cmp(vector<int> &A, vector<int> &B) {
  if (A.size() != B.size()) return A.size() > B.size();
  // 元素相等的情况下，就要比较第 1 个不等的元素，从高位开始比较
  for (int i = A.size() - 1; i >=0; i--) {
    if (A[i] != B[i]) return A[i] > B[i];
  }
  // 每一位 A[i]  和 B[i] 都相等
  return true;
}

// 逐位相减得到结果，前提是 A >= B
vector<int> sub(vector<int> &A, vector<int> &B) {
  vector<int> C;
  
  for (int i = 0, t = 0; i < A.size(); i++) {
    t = A[i] - t;
    if (i < B.size()) t -= B[i];
    
    // if (t >= 0) C.push_back(t % 10);
    // else C.push_back((t + 10) % 10);
    
    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 s1, s2;
    cin >> s1 >> s2;
    
    vector<int> A, B;
    
    for (int i = s1.size() - 1; i >=0 ; i--) {
      A.push_back(s1[i] - '0');
    }
    
    for (int i = s2.size() - 1; i >=0 ; i--) {
      B.push_back(s2[i] - '0');
    }
    
    if (cmp(A, B)) {
       vector<int> C = sub(A, B); // 调用高精度的减法运算函数
       for (int i = C.size() - 1; i >= 0; i--) cout << C[i];
    } else {
      vector<int> C = sub(B, A);
      cout << "-";
      for (int i = C.size() - 1; i >= 0; i--) cout << C[i];
    }
  
    return 0;
}

高精度乘法 A×b

这里讨论的高精度乘法是 A × b 形式，也就是高精度大数乘以低精度小数的情况。

方法一：数组实现

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 250; // 240位+进位空间

int main() {
    string a;  // 存储大整数a
    int b;     // 存储小整数b
    cin >> a >> b;
    
    if (b == 0) {  // 特殊情况处理
        cout << 0;
        return 0;
    }
    
    int len = a.size();
    int num[MAXN] = {0};  // 存储大整数的各位数字（逆序）
    int result[MAXN] = {0}; // 存储结果
    
    // 将字符串逆序存储到整型数组中
    for (int i = 0; i < len; i++) {
        num[i] = a[len - 1 - i] - '0';
    }
    
    // 逐位相乘
    int carry = 0;  // 进位
    for (int i = 0; i < len; i++) {
        int temp = num[i] * b + carry;
        result[i] = temp % 10;
        carry = temp / 10;
    }
    
    // 处理最高位进位
    while (carry > 0) {
        result[len] = carry % 10;
        carry /= 10;
        len++;
    }
    
    // 逆序输出结果
    for (int i = len - 1; i >= 0; i--) {
        cout << result[i];
    }
    
    return 0;
}

方法二：字符串直接实现

我们可以直接使用字符串来表示大整数，并通过字符串操作来实现乘法运算，避免使用数组。基本思路是：

逆序字符串：将大整数字符串逆序，方便从低位开始计算
逐位相乘：对每一位数字进行乘法运算
处理进位：将进位传递到下一位
恢复顺序：最后将结果字符串逆序回来

#include <bits/stdc++.h>
using namespace std;

string multiply(string a, int b) {
    if (b == 0) return "0";  // 任何数乘以0等于0
    
    reverse(a.begin(), a.end());  // 反转字符串，从低位开始处理
    string result;
    int carry = 0;
    
    for (int i = 0; i < a.size(); i++) {
        int digit = (a[i] - '0') * b + carry;
        result.push_back((digit % 10) + '0');  // 当前位数字
        carry = digit / 10;  // 计算进位
    }
    
    // 处理剩余的进位
    while (carry > 0) {
        result.push_back((carry % 10) + '0');
        carry /= 10;
    }
    
    reverse(result.begin(), result.end());  // 反转回正常顺序
    
    // 去除前导零（如果有）
    size_t nonZero = result.find_first_not_of('0');
    if (nonZero != string::npos) {
        return result.substr(nonZero);
    }
    return "0";
}

int main() {
    string a;
    int b;
    cin >> a >> b;
    cout << multiply(a, b) << endl;
    return 0;
}

方法三：vector 实现

#include <bits/stdc++.h>
using namespace std;


vector<int> mul(vector<int> &A, int b) {
  vector<int> C;
  
  int t = 0;
  
  // 手动计算乘法，注意每一次是乘整个 b
  for (int i = 0; i < A.size(); i++) {
    t += A[i] * b; 
    C.push_back(t % 10);
    t /= 10;
  }
  
  if (t) C.push_back(t);
  
  return C;
}

int main() {
    string s1;
    int b;
    cin >> s1 >> b;
    
    vector<int> A;
    
    for (int i = s1.size() - 1; i >= 0; i--) {
      A.push_back(s1[i] - '0');
    }
    
    auto C = mul(A, b);
    
    for (int i = C.size() - 1; i >= 0; i--) cout << C[i];
    
    return 0;
}

高精度除法 A÷b

这里是 A ÷ b 的形式，也就是高精度大数除以低精度小数。

#include <bits/stdc++.h>
using namespace std;

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());
  
  while (C.size() > 1 && C.back() == 0) C.pop_back();
  
  return C;
}

int main() {
    string s1;
    int b;
    cin >> s1 >> b;
    
    vector<int> A;
    
    for (int i = s1.size() - 1; i >= 0; i--) {
      A.push_back(s1[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;
}

高精度 2 的 n 次幂

求 2 的 n 次幂，其中 $n \le 50$ ，由于次幂的结果递增很快，结果也没办法用 long long 来表示，也属于高精度问题。

#include <bits/stdc++.h>
using namespace std;

const int N = 3000;

int main() {
    
    int a[N] = {1};
    int m = 1;
    int n;
    cin >> n;
  
    for (int i = 0; i < n; i++) {
      int t = 0;
      for (int j = 0; j < m; j++) {
        t += a[j] * 2;
        a[j] = t % 10;
        t /= 10;
      }
      if (t) a[m++] = 1;
    }
    
    for (int i = m-1; i >=0; i--) {
      cout << a[i];
    }
    
    cout << endl;
    
    return 0;
}

综合示例：求解 Pell 数列

题目描述

有一种数列，它的前10项的值分别为：1 2 5 12 29 70 169 408 985 2378，这个数列被称为Pell数列，请问该数列的第n项的值是多少？ $n \le 100$

输入描述

一个整数n。

输出描述

第n项的值。

输入数据

输出数据

题目解析

Pell 数列这个题目实际上是一个结合递推与高精度的综合性任务，难点在于：

首先需要找出数字序列的规律（得出递推关系）
涉及到高精度加法与高精度乘法的结合使用

通过观察题目，可以找出该数字序列的规律：从第 3 项开始，每一项（第 n 项）的值等于它前面一项（第 n-1 项）的值的两倍，再加上它往前再一项（第 n-2 项）的值。递推公式如下：

$A_{n} = A_{n-1} * 2 + A_{n-2}$

因此原问题可以拆成两个小问题：

$A_{n-1} * 2$ 是一个高精度乘法问题（下面的 mul() 函数实现）
$A_{n-1} * 2 + A_{n-2}$ 是一个高精度加法问题（下面的 add() 函数实现。

代码实现

#include <bits/stdc++.h>
using namespace std;

// 高精度 + 高精度
string add(string s1, string s2) {
  string r; // 存放最终的求和结果
  int a[1000] = {0};
  int b[1000] = {0};
  int c[1000] = {0};
  
  int len = max(s1.size(), s2.size());
  
  for (int i = s1.size() - 1, j = 0; i >= 0; i--, j++) {
    a[j] =s1[i] - '0';
  }
  
  for (int i = s2.size() - 1, j = 0; i >= 0; i--, j++) {
    b[j] =s2[i] - '0';
  }
  
  int t = 0; // 代表加法进位
  for (int i = 0; i < len; i++) {
    t = a[i] + b[i] + t;
    c[i] = t % 10;
    t = t / 10;
  }
  
  if (t > 0) c[len++] = t;
  
  for (int i = 0; i < len; i++) {
    r = char(c[i] + '0') + r;
  }
  
  return r;
}

// 高精度 × 2
string mul(string s) {
  string r;
  int a[1000] = {0};
  int c[1000] = {0};
  int len = s.size();
  
  for (int i = len - 1, j = 0; i >= 0; i--, j++) {
    a[j] = s[i] - '0';
  }
  
  int t = 0;
  for (int i = 0; i < len; i++) {
    t = t + a[i] * 2;
    c[i] = t % 10;
    t = t / 10;
  }
  
  if (t > 0) c[len++] = t;
  
  for (int i = 0; i < len; i++) {
    r = char(c[i] + '0') + r;
  }
  
  return r;
}

int main() {
  
  string x, y, z;
  int n;
  cin >> n;
  
  // 递推公式 A(n) = A(n-1) * 2 + A(n-2)
  x = "1";
  y = "2";
  
  // 递推实现
  if (n == 1) cout << x << endl;
  else if (n == 2) cout << y << endl;
  else {
    for (int i = 3; i <= n; i++) {
      z = add(mul(y), x);
      x = y;
      y = z;
    }
  }
  
  cout << z << endl;
  return 0;
}

拓展思考

需要注意的是，我们这里在两个计算高精度加法和乘法的函数里，是用数组来处理的，以上面的 add() 加法为例：

int a[1000] = {0};
int b[1000] = {0};
int c[1000] = {0};

这里的 a、b、c 都是函数 add() 的局部变量，在 C++ 中局部变量是分配在栈上的，有大小限制，如果我们开的数组特别大，比如 $10^6$ 大小，容易爆栈，因此如果数据位数特别大，可以用 vector 来替代这里的数组。

实际上，题目中要求的 Pell 数列的第 $n$ 项结果是：

66992092050551637663438906713182313772

粗略一看，都不会超过 50 位，我们程序里设定 1000 位的数已经远超过这个数了。

当然，你也可以用 vector 来实现，代码如下：

3zjexa72j - C++ - OneCompiler

#include <bits/stdc++.h>
using namespace std;

// 高精度 + 高精度
string add(string s1, string s2) {
  string r; // 存加的结果
  
  vector<int> v1, v2, v3;
  
  for (int i = s1.size() - 1; i >= 0; i--) {
    v1.push_back(s1[i] - '0');
  }
  
  for (int i = s2.size() - 1; i >= 0; i--) {
    v2.push_back(s2[i] - '0');
  }
  
  int t = 0;
  // 注意这里 v1 的 size 一定是较大的
  for (int i = 0; i < v1.size(); i++) {
    t = t + v1[i];
    if (i < v2.size()) t = v2[i] + t;
    v3.push_back(t % 10);
    t = t / 10;
  }
  
  if (t > 0) v3.push_back(t);
  
  for (int i = 0; i < v3.size(); i++) {
    r = char(v3[i] + '0') + r;
  }
  
  return r;
}

string mul(string s) {
  string r;
  vector<int> v1, v2;
  
  for (int i = s.size() - 1; i >= 0; i--) {
    v1.push_back(s[i] - '0');
  }
  
  int t = 0;
  for (int i = 0; i < v1.size(); i++) {
    t = t + v1[i] * 2;
    v2.push_back(t % 10);
    t = t / 10;
  }
  
  if (t > 0) v2.push_back(t);
  
  for (int i = 0; i < v2.size(); i++) {
    r = char(v2[i] + '0') + r;
  }
  
  return r;
}


int main() {
  string x, y, z; 
  int n;
  cin >> n;
  
  x = "1";
  y = "2";
  
  if (n == 1) cout << x << endl;
  else if (n == 2) cout << y << endl;
  else {
    for (int i = 3; i <= n; i++) {
      z = add(mul(y), x);
      x = y;
      y = z;
    }
  }
  
cout << z << endl;
 return 0;
}

需要注意在做加法时，因为 v1 和 v2 是动态的大小，如果两个数位数不一致，就会遇到加一个不存在位置的元素，就会带来问题，从题目已知条件来看，v1.siz() 一定比 v2.size() 更大，因此我们在按位加的时候稍做处理即可。

int t = 0;
  // 注意这里 v1 的 size 一定是较大的
  for (int i = 0; i < v1.size(); i++) {
    t = t + v1[i];
    if (i < v2.size()) t = v2[i] + t;
    v3.push_back(t % 10);
    t = t / 10;
  }

小结

通过高精度算法，我们可以处理超出标准数据类型范围的数值运算，实现的方法主要是利用字符串和数组来存储大数的每一位，在运算时从低到高位逐位计算，计算完成后再逐位输出，在计算时，需要特别注意进位与借位的处理。

除了大数运算外，高精度算法还常用于密码学、计算几何、组合数学及科学计算等领域。

ON THIS PAGE

#高精度算法

#高精度运算基本思路

#高精度加法 A+B

#方法一：数组实现

#方法二：字符串实现

#高精度减法 A-B

#实现步骤

#代码实现

#高精度乘法 A×b

#方法一：数组实现

#方法二：字符串直接实现

#方法三：vector 实现

#高精度除法 A÷b

#高精度 2 的 n 次幂

#综合示例：求解 Pell 数列

#题目解析

#代码实现

#拓展思考

#小结

高精度算法

高精度运算基本思路

高精度加法 A+B

方法一：数组实现

方法二：字符串实现

高精度减法 A-B

实现步骤

代码实现

高精度乘法 A×b

方法一：数组实现

方法二：字符串直接实现

方法三：vector 实现

高精度除法 A÷b

高精度 2 的 n 次幂

综合示例：求解 Pell 数列

题目解析

代码实现

拓展思考

小结