C++ 高精度算法

zltzlt

高精度算法

高精度数

计算机数据范围的表示有一定限制。如整型 int、无符号整型的表达范围都约为几十亿。

而实数型中，能保存最多位数的双精度型 double 也只能提供 15~16 位的有效数字，只能精确地表达十多位的数。

因此，在计算位数超过十几位的数时，不能采用现有类型，只能自己编程计算。这就是高精度算法。

高精度算法使用计算机对于超大数据的一种模拟加、减、乘、除、乘方、阶乘、开方等运算的算法。

一般来说，对于非常庞大的数字无法在计算机中正常存储。

于是我们将这个数字拆开，拆成一位一位的存储到数组中，用一个数组去表示一个数字，这样这个数字就被称为是高精度数。

高精度数存储

高精度数一般有两种输入方法，分别是：

• 采用字符串形式输入
• 直接输入
  

1. 采用字符串形式输入（常用）

1. #include <iostream>
   
2. #include <cstring>
   
3. 
   
4. using namespace std;
   
5. const int N = 100; // 最多一百位
   
6. 
   
7. int main()
   
8. {
   
9.     int a[N + 1], i;
   
10.     string s;
    
11.     getline(cin, s);
    
12.     memset(a, 0, sizeof(a)); // 数组清零
    
13.     a[0] = s.size();         // 位数
    
14.     for (i = 1; i <= a[0]; i++)
    
15.         a[i] = s[a[0] - i] - '0'; // 将字符串转为数字并倒序存储
    
16.     return 0;
    
17. }

复制代码

2. 直接输入

1. #include <iostream>
   
2. 
   
3. using namespace std;
   
4. const int N = 100; // 最多一百位
   
5. 
   
6. int main()
   
7. {
   
8.     int a[N + 1] = {}, i = 0, s;
   
9.     long long key;
   
10.     cin >> key;
    
11.     while (key)
    
12.     {
    
13.         a[++i] = key % 10;
    
14.         key = key / 10;
    
15.     }
    
16.     a[0] = i;
    
17.     return 0;
    
18. }

复制代码

高精度数比较

1. int compare(int a[], int b[])
   
2. {
   
3.     /* 比较 a 和 b 的大小关系，若 a > b 则返回 1，a < b 则返回 -1，a == b 则返回 1 */
   
4.     int i;
   
5.     if (a[0] > b[0])
   
6.         return 1; // a 的位数大于 b 的位数，则 a 比 b 大
   
7.     if (b[0] > a[0])
   
8.         return -1; // b 的位数大于 a 的位数，则 b 比 a 大
   
9.     for (i = a[0]; i > 0; i--)
   
10.     {
    
11.         cout << a[i] << " " << b[i] << endl;
    
12.         if (a[i] > b[i])
    
13.             return 1;
    
14.         if (a[i] < b[i])
    
15.             return -1;
    
16.     }
    
17.     return 0; // 各位都相等则两数相等
    
18. }

复制代码

普通整型数转化为高精度数

1. int *convert(unsigned long long n)
   
2. {
   
3.     /* 将非负整数转化成高精度数 */
   
4.     int i, dg, *r = (int *)malloc(digit + 1);
   
5.     if (n < 10)
   
6.         dg = 1;
   
7.     else
   
8.     {
   
9.         i = 2;
   
10.         for (;; i++)
    
11.         {
    
12.             if (n < pow(10, i))
    
13.             {
    
14.                 dg = i;
    
15.                 break;
    
16.             }
    
17.         }
    
18.     }
    
19.     r[0] = dg;
    
20.     for (i = 1; i <= dg; i++)
    
21.         r[i] = n % int(pow(10, i)) / int(pow(10, i - 1));
    
22.     return r;
    
23. }

复制代码

高精度数加法

1. int *add(int a[], int b[])
   
2. {
   
3.     /* 计算 a + b 并返回 */
   
4.     int i = 1, k = a[0] > b[0] ? a[0] : b[0], *r = (int *)malloc(digit + 1); // k 是 a 和 b 中位数最大的数的位数
   
5.     for (; i <= k; i++)
   
6.     {
   
7.         r[i + 1] = a[i + 1] + (a[i] + b[i]) / 10; // 有进位，先进位
   
8.         r[i] = (a[i] + b[i]) % 10;                // 计算当前位数字
   
9.     }
   
10.     if (r[k + 1] > 0)
    
11.         r[0] = k + 1; // 修正新的数字的位数
    
12.     else
    
13.         r[0] = k;
    
14.     return r;
    
15. }

复制代码

高精度数减法

1. int *sub(int a[], int b[])
   
2. {
   
3.     /* 计算 a - b 并返回，如果 a < b 或 a == b 则返回 0 */
   
4.     int flag = compare(a, b), i = a[0], *r = (int *)malloc(digit + 1); // 调用比较函数比较大小
   
5.     if (flag != 1)
   
6.     {
   
7.         r[0] = 1;
   
8.         r[1] = 0;
   
9.         return r;
   
10.     }
    
11.     r[0] = a[0];
    
12.     for (; i > 0; i--)
    
13.         r[i] = a[i];
    
14.     for (i = 1; i <= a[0]; i++)
    
15.     {
    
16.         if (a[i] < b[i])
    
17.         {
    
18.             // 不够减，向上借 1
    
19.             r[i + 1]--;
    
20.             r[i] += 10;
    
21.         }
    
22.         r[i] = r[i] - b[i];
    
23.     }
    
24.     while (!r[r[0]])
    
25.         r[0]--; // 修正 r 的位数
    
26.     return r;
    
27. }

复制代码

高精度数乘法

1. int *mul(int a[], int b[])
   
2. {
   
3.     int i, j, *r = (int *)malloc(digit + 1);
   
4.     memset(r, 0, sizeof(r));
   
5.     for (i = 1; i <= a[0]; i++)
   
6.     {
   
7.         for (j = 1; j <= b[0]; j++)
   
8.         {
   
9.             r[i + j - 1] = r[i + j - 1] + a[i] * b[j];
   
10.             r[i + j] = r[i + j] + r[i + j - 1] / 10;
    
11.             r[i + j - 1] = r[i + j - 1] % 10;
    
12.         }
    
13.     }
    
14.     r[0] = a[0] + b[0];
    
15.     if (r[r[0]] == 0)
    
16.         r[0]--;
    
17.     return r;
    
18. }

复制代码