高精度原理介绍及代码实现

高精度算法（High Accuracy Algorithm）的出现是为了处理超大数据的数学计算问题。在一般的科学计算中，我们可能会遇到需要计算小数点后几百位甚至更多的数字，或者处理几千亿、几百亿这样的大数字。这些数字超出了标准数据类型（如整型、实型）能够表示的范围，因此无法直接在计算机中正常存储和计算。

实现原理

在高精度算法中，我们并不会把数据用int，long long,double这种数据结构来存储，而是用数组来存储，接下来我就讲讲其原理

高精度加法

数据存储

先从简单的加减运算说起，我们拿 23 + 25这个例子来举例，根据小学所学知识，我们知道当我们计算时应该列出这样子的式子：

如果我们要进行加法，那么我们将从右加到左，一一进位

而我们的算法将这里的27处理为：A[2] = {7,2};25处理为：B[2] = {5,2};

他们的和仍然是一个数组：C[2] = {2, 5};

你可能好奇，为什么是倒着存？🧐🤨

俺在前面也说过：从右加到左，因此，当我倒着存时，最低位（27的最低位为7）就在A[0],而当A[0] + B[0]要进位时，进位的1就被加到了C[1]，综上所述，倒着存是为了方便进位（i进的位直接存在了i + 1的位置）(也就是7 + 5进的位存在了C[1])

倒着存应该怎么写呢？🤨🤨🤨

很简单，我们要注意读入数据时不能把存数据的变量设置为int,long long了，而是要设置为string

//a + b = c

int A[505];//第一个加数的数组
int B[505];//第二个加数的数组
int C[506];//和的数组
int len_c;
int main()
{
    string a, b;//注意用字符串读入
    cin >> a >> b;

    int len_a = a.size(), len_b = b.size();//len_a表示a有几个数字（若a = 1,则len_a = 1,若a = 10,则len_a = 2）
    int len_c = max(len_a, len_b);//a 和 b的和c最初设置为a 和 b的最大值，因为要确保每位都参与加法，就得让位数多的每位都加上
    
    //逆序存
    for (int i = 0; i < len_a; i++)
        A[len_a - 1 - i] = a[i] - '0';//注意 - ‘0’，因为是字符读入，且逆序存
    for (int i = 0; i < len_b; i++)
        B[len_b - 1 - i] = b[i] - '0';//注意 - ‘0’
    Add();
    
    return 0;
}

接下来就是重要的加法实现了

加法实现

先看代码

void Add()
{
    for (int i = 0; i < len_c; i++)
    {
        C[i] += A[i] + B[i];
        C[i + 1] += C[i] / 10;
        C[i] %= 10;
    }

    if (C[len_c])
        len_c++;
}

for循环：for循环是从0开始的，这是因为我们存储的时候0位放的就是加数的最低位（27的7）
A[i] + B[i]:模仿传统加法（我们例子中就是：7 + 5）
C[i + 1] += C[i] / 10;：模仿进位（我们例子中就是：(7 + 5) / 10 = 1,因此在C[1]上进位了1）
C[i] %= 10; : 本位进位完后就要变为只有个位（我们例子中就是：(7 + 5) /%10 = 2,因此在C[0]上只有2）
if (C[len_c]) len_c++;:如果结果中最高位下一位不为0，说明len_c的长度要++

如同：

9 7 + 3，在len_c = max(len_a, len_b);后，len_c的长度为2，但是当计算完97 + 3 = 100后：之前的最高位（第二位）的下一位（第三位）不为0（100的1），长度变为3，因此要更新len_c

没想到吧，到这里就把高精度讲完啦，你看到这里很棒了哦，给你一个赞 d=====(￣▽￣*)b

总代码

//a + b = c

int A[505];//第一个加数的数组
int B[505];//第二个加数的数组
int C[506];//和的数组
int len_c;

void Add()
{
    for (int i = 0; i < len_c; i++)
    {
        C[i] += A[i] + B[i];
        C[i + 1] += C[i] / 10;
        C[i] %= 10;
    }

    if (C[len_c])
        len_c++;
}

int main()
{
    string a, b;//注意用字符串读入
    cin >> a >> b;

    int len_a = a.size(), len_b = b.size();
    len_c = max(len_a, len_b);
    for (int i = 0; i < len_a; i++)
        A[len_a - 1 - i] = a[i] - '0';//注意 - ‘0’，且逆序存
    for (int i = 0; i < len_b; i++)
        B[len_b - 1 - i] = b[i] - '0';//注意 - ‘0’

    Add();

    for (int i = 0; i < len_c; i++)
        cout << C[len_c - 1 - i];//注意逆序输出，因为存的时候是逆序的
    return 0;
}

高精度减法

这也是类似的，高精度通用的就是：

数据用字符串读入，用数组存数
要倒着存储数据
注意进位
注意逆序输出

与加法的不同点:

敲重点了哦~ψ(｀∇´)ψ

要看两个数据谁更大，要把大的作为a,小的作为b
若起初a < b,要用标记标记该答案为负数，以便最后得出答案时输出符号

总代码

//与加法相似
//加了调转字符串的操作
int main()
{
    string str1, str2;
    cin >> str1;
    cin >> str2;

    //两个数字最大为10^10086，因此数组设为10088就可（咱图个吉利）
    int a[10088] = { 0 }, b[10088] = { 0 }, c[10088] = { 0 };
    
    int flag = 0;
    //标记是否进行了调转字符串

    //与加法不同的是减法要调转字符串，把位数多的放前面，方便计算
    //至于负号，可以先标记，最后再进行处理

    if (str2.size() > str1.size()/*如果起初的b > a,---->要调转a, b, 把原先的a 变为 b*/||(str2.size() == str1.size()&&str1<str2))
    {
        /*!!!!!!!!!!!!!!!!!!!!注意或者后面的情况，若只有或者前面部分的，若是3-4这种情况，则无法算出正确答案*/
        //str1<str2:前者的数字小于后面的数，虽然这是字符串，但仍然可以这样比较
        flag = 1;
        //标记进行了调换:方便最后输出 - 号
        swap(str1, str2);
        //调转的函数，具体的大家可以去自行了解
    }

    for (int i = 0; i < str1.size(); i++)
    {
        a[i] = str1[str1.size() - 1 - i] - '0';
        //减'0'别忘了
    }

    for (int i = 0; i < str2.size(); i++)
    {
        b[i] = str2[str2.size() - 1 - i] - '0';
    }

    //因为一开始就进行了调换最长的数放在str1，所以这里不需要取str1和str2中最长的赋值给len
    for (int i = 0; i < str1.size(); i++)
    {
        c[i] = a[i] - b[i];
        if (c[i] < 0)
        {
            a[i + 1]--;
            c[i] = a[i] + 10 - b[i];
            //记得给a[i]加10，就是模拟实际的计算
        }
    }

    //因为一开始就进行了调换最长的数放在str1，所以这里不需要取str1和str2中最长的赋值给len,叶不用进行len++
    //直接判断是否要进行len--
    int len = str1.size();

    /*是while，不是if*/

    while(c[len - 1] == 0 && len > 1)
        len--;


    if (flag == 1)//输出负号
        printf("-");
    for (int i = 0; i < len; i++)//仍然是倒着输出
    {
        printf("%d", c[len - 1 - i]);
    }
    printf("\n");

    return 0;
}

高精度乘法

总代码

int c[5000];
int len_a, len_b, len_c;
void mul(int a[], int b[])
{
    for (int i = 0; i < len_a; i++)
    {
        for (int j = 0; j < len_b; j++)
        {
            c[i + j] += a[i] * b[j];//注意是 +=
            c[i + j + 1] += c[i + j] / 10;
            c[i + j] = c[i + j] % 10;
        }
    }

    while (len_c > 1 && c[len_c - 1] == 0)
    //注意要len_c > 1，如果乘积为0，就会一直减下去，最后什么都不输出，这是错误的
    //注意是c[len_c - 1] == 0
        len_c--;
}

int main()
{
    string a, b;
    cin >> a >> b;
    len_a = a.size(), len_b = b.size();
    len_c = len_a + len_b;
    int aarr[2005], barr[2005];

    //倒着存
    for (int i = 0; i < len_a; i++)
        aarr[i] = a[len_a - 1 - i] - '0';//记得 - '0'
    for (int i = 0; i < len_b; i++)
        barr[i] = b[len_b - 1 - i] - '0';
    
    mul(aarr, barr);

    //cout << len_c << endl;
    //倒着输出
    for (int i = 0; i < len_c; i++)
        cout << c[len_c - 1 - i];
    return 0;
}

高精度除法

脑子不好的小菜鸟正在学习中::>_<::

总结

总注意点

综上所述，所谓的高精度就是模仿传统的运算法则，注意总点如下：

不用数据类型存储数据，因为计算机存不下那么大的数字
用数组存储，且逆序存储

注意进位,还有前置0

（如：100 - 90 = 010,这个最高位的0是不输出的，要用如下句子处理掉：

while (len_c > 1 && c[len_c - 1] == 0)
    //注意要len_c > 1，如果答案为0，就会一直减下去，最后什么都不输出，这是错误的
    //注意是c[len_c - 1] == 0
        len_c--;

）

减法注意点

要看两个数据谁更大，要把大的作为a,小的作为b
若起初a < b,要用标记标记该答案为负数，以便最后得出答案时输出符号

原文地址:https://blog.csdn.net/2301_79293429/article/details/138774976 本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：https://www.suanlizi.com/kf/1789777105064693760.html 如若内容造成侵权/违法违规/事实不符，请联系《酸梨子》网邮箱：1419361763@qq.com进行投诉反馈，一经查实，立即删除！

阅读全部