C++ 高精度数计算

zltzlt

高精度数计算

头文件 high_pre.h：

#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cmath>

using namespace std;
const int digit = 10000; // 最多一万位

int *input(string prompt = "")
{
    /* 询问用户输入高精度数 */
    int *a = (int *)malloc(digit + 1), i;
    string s;
    cout << prompt;
    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 a;
}

void print(int num[], string end = "\n")
{
    /* 打印高精度数 */
    int i = num[0];
    for (; i > 0; i--)
        cout << num[i];
    cout << end;
}

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--)
    {
        if (a[i] > b[i])
            return 1;
        if (a[i] < b[i])
            return -1;
    }
    return 0; // 各位都相等则两数相等
}

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] -= b[i];
        if (r[i] < 0)
        {
            r[i + 1]--;
            r[i] += 10;
        }
    }
    while (!r[r[0]])
        r[0]--; // 修正 r 的位数
    return r;
}

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 *mul(int a[], int b[])
{
    /* 计算 a * 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]])
        r[0]--;
    return r;
}

int *div_int(int a[], int b)
{
    /* 计算 a / b（b 不为高精度数） */
    int *r = (int *)malloc(digit + 1), k = a[0], i, d = 0;
    memset(r, 0, sizeof(r));
    for (i = k; i >= 0; i--)
    {
        d = d * 10 + a[i];
        if (!d)
            continue;
        r[i] = d / b;
        d %= b;
    }
    while (!r[k] && k)
        k--;
    r[0] = k;
    return r;
}