C++ 高精度算法

zltzlt

高精度算法

高精度数

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

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

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

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

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

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

高精度数存储

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

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

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

#include <iostream>
#include <cstring>

using namespace std;
const int N = 100; // 最多一百位

int main()
{
    int a[N + 1], i;
    string s;
    getline(cin, s);
    memset(a, 0, sizeof(a)); // 数组清零
    a[0] = s.size();         // 位数
    for (i = 1; i <= a[0]; i++)
        a[i] = s[a[0] - i] - '0'; // 将字符串转为数字并倒序存储
    return 0;
}

2. 直接输入

#include <iostream>

using namespace std;
const int N = 100; // 最多一百位

int main()
{
    int a[N + 1] = {}, i = 0, s;
    long long key;
    cin >> key;
    while (key)
    {
        a[++i] = key % 10;
        key = key / 10;
    }
    a[0] = i;
    return 0;
}

高精度数比较

int compare(int a[], int b[])
{
    /* 比较 a 和 b 的大小关系，若 a > b 则返回 1，a < b 则返回 -1，a == b 则返回 1 */
    int i;
    if (a[0] > b[0])
        return 1; // a 的位数大于 b 的位数，则 a 比 b 大
    if (b[0] > a[0])
        return -1; // b 的位数大于 a 的位数，则 b 比 a 大
    for (i = a[0]; i > 0; i--)
    {
        cout << a[i] << " " << b[i] << endl;
        if (a[i] > b[i])
            return 1;
        if (a[i] < b[i])
            return -1;
    }
    return 0; // 各位都相等则两数相等
}

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

int *convert(unsigned long long n)
{
    /* 将非负整数转化成高精度数 */
    int i, dg, *r = (int *)malloc(digit + 1);
    if (n < 10)
        dg = 1;
    else
    {
        i = 2;
        for (;; i++)
        {
            if (n < pow(10, i))
            {
                dg = i;
                break;
            }
        }
    }
    r[0] = dg;
    for (i = 1; i <= dg; i++)
        r[i] = n % int(pow(10, i)) / int(pow(10, i - 1));
    return r;
}

高精度数加法

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

高精度数减法

int *sub(int a[], int b[])
{
    /* 计算 a - b 并返回，如果 a < b 或 a == b 则返回 0 */
    int flag = compare(a, b), i = a[0], *r = (int *)malloc(digit + 1); // 调用比较函数比较大小
    if (flag != 1)
    {
        r[0] = 1;
        r[1] = 0;
        return r;
    }
    r[0] = a[0];
    for (; i > 0; i--)
        r[i] = a[i];
    for (i = 1; i <= a[0]; i++)
    {
        if (a[i] < b[i])
        {
            // 不够减，向上借 1
            r[i + 1]--;
            r[i] += 10;
        }
        r[i] = r[i] - b[i];
    }
    while (!r[r[0]])
        r[0]--; // 修正 r 的位数
    return r;
}

高精度数乘法

int *mul(int a[], int b[])
{
    int i, j, *r = (int *)malloc(digit + 1);
    memset(r, 0, sizeof(r));
    for (i = 1; i <= a[0]; i++)
    {
        for (j = 1; j <= b[0]; j++)
        {
            r[i + j - 1] = r[i + j - 1] + a[i] * b[j];
            r[i + j] = r[i + j] + r[i + j - 1] / 10;
            r[i + j - 1] = r[i + j - 1] % 10;
        }
    }
    r[0] = a[0] + b[0];
    if (r[r[0]] == 0)
        r[0]--;
    return r;
}