高精度算法

为什么要有高精度运算？因此计算机内部我们常用的数据类型能表示的范围都是有限的，比如 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 × b，其中 A 为「大数」，b 为普通的可以用 int 表示的数
• 计算 A ÷ b，其中 A 为「大数」，b 为普通的可以用 int 表示的数，且 b 不等于 0

高精度运算基本思路

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

高精度加法

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

例如：

65476547645485485486859675132
76528989565454376596796475347

方法一：数组实现

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

实现代码：

• 3zgb4g36p - C++ - OneCompiler

#include <iostream>
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;
}

方法二：字符串实现

• 42gh26f5w - C++ - OneCompiler

充分利用了字符串的特点。

// 高精度加法（字符串实现）
#include <bits/stdc++.h>
using namespace std;

string s1, s2;

string add(string s1, string s2) {
  int t = 0, sum = 0; // t 为进位，sum 求和
  int len1 = s1.size();
  int len2 = s2.size();

  string rlt = "";
  char c;
  while (len1 > 0 || len2 > 0 || t > 0) {
    sum = t;
    if (len1 > 0) sum += s1[--len1] - '0';
    if (len2 > 0) sum += s2[--len2] - '0';
    t = sum / 10;
    c = sum % 10 + '0';
    rlt = c + rlt;
  }

  return rlt;

}

int main() {
  cin >> s1 >> s2;

  cout << add(s1, s2) << endl;
  return 0;
}

高精度减法

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

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

例如：

76528989565454376596796475347
65476547645485485486859675132

问题解析

在进行高精度减法运算时，需要注意下面几点：

1. 我们这里只考虑了两个非负整数相减的情况
2. 用 vector 替代了 array，用法与数组差不多，但更灵活一些
3. 大数减小数。如果是小数减大数，调整为大数减小数，在结果前添加负号 -
4. 对前导 0 做了处理，例如 123 - 120，如果不处理结果将是 003

基本步骤

以下是使用C++实现高精度减法的步骤：

1. 输入两个数字：按字符串读入两个非负整数，并将两个非负整数转换为vector<int>。
2. 确定大数和小数：如果需要，交换两个数字，确保大数在前。
3. 进行减法运算：从最低位开始，逐位进行减法运算，注意借位。
4. 处理结果：如果结果为负数，添加负号；去除前导零。

代码实现：

• 3yujwr7uq - C++ - OneCompiler

#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();
  // 元素相等的情况下，就要比较第 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;
}

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 ���形式，也就是高精度大数乘以低精度小数。

• 3yujhtmzv - C++ - OneCompiler

#include <iostream>
#include <vector>
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 的形式，也就是高精度大数除以低精度小数。

• 3zgb8z9hn - C++ - OneCompiler

#include <iostream>
#include <vector>
#include <algorithm>

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$ 。

• 3ysh4wgn3 - C++ - OneCompiler

#include <iostream>
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项的值。

样例

输入复制

10

输出复制

2378

题目解析

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() 函数实现。

代码实现

• 3zh7mmwdp - C++ - OneCompiler

#include <iostream>
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;
  }

小结

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

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