高精度计算

高精度计算

smallfang

2020 年 08 月 25 日

726 次浏览

暂无评论

481字数

算法笔记

这篇文章撰写于博客重置前。个人认为是原来写的博客中最好的[heimu]可见其他文章写的更菜[/heimu]。

概念

我们先从一个问题开始
(任何一个伟大的思想，都有一个微不足道的开始。)
Q:高精度是什么？
C++:实现更多位数的计算。科技是在进步的qwq
Java:同上
~~Python:啥?为啥要写高精度~~

那么我们来研究C++的高精度。

实现

四则运算之加法:

我们按照小学生的竖式计算法将两个数相加。（两个数可以使用字符串或整形数组）

代码永远是最直观的。 -----不(wo)知(shuo)道(de)

代码：

string add(char x[],char y[])
{
    int l1=strlen(x);
    reverse(x,x+l1);
    int l2=strlen(y);
    reverse(y,y+l2);
    int lm=max(l1,l2);
    for(int i=0;i<lm;++i)
    {
        if(x[i]==NULL)x[i]='0';
        if(y[i]==NULL)y[i]='0'; 
        x[i]=x[i]-'0';
        y[i]=y[i]-'0';
    }
    string ans;
    int j=0;
    for(int i=0;i<lm;++i)
    {
        j=x[i]+y[i]+j;
        if(j>=10)ans=ans+char(j-10),j=1;
        else ans=ans+char(j),j=0;
    }
    int l=ans.size();
    ans=ans+char(j);
    for(int i=l-1+j;i>=0;--i)
    {
        cout<<char(ans[i]+'0');
    }
    return "y";
}

四则运算之减法：

与加法相对。但要注意负数可能性。

void sub(char a[],char b[])
{
    int ans[200008];
    int l1=strlen(a);
    int l2=strlen(b);
    reverse(a,a+l1);
    reverse(b,b+l2);
    int lm=max(l1,l2); 
    for(int i=0;i<lm;++i)
    {
        if(a[i]==NULL)a[i]='0';
        if(b[i]==NULL)b[i]='0'; 
        a[i]=a[i]-'0';
        b[i]=b[i]-'0';
    }
    int j=0; 
    for(int i=0;i<lm;i++)
    {
        j=(a[i]-b[i])-j;
        if(j<0){ans[i]=j+10,j=1;}
        else ans[i]=j,j=0;
    }
    if(j)cout<<"-";
    bool flag=false;
    for(int i=lm;i>=0;--i)
    {
        if(ans[i])flag=true;
        if(flag)
        cout<<char(ans[i]+'0');
     } 
     if(flag==false)cout<<"0";
 }

四则运算之乘法

请您重点关注下面文章内容，重点部分以分割线结束。

我们来到了重点。在此节我们需要快速写出高精度乘法。

其代码重点是
c[i+j]=a[i]*a[j];
我们该如何理解呢?
最后的结果上标和是有规律的。
所以我们仍然可以验证c[i+j]=a[i]*a[j]是正确的。

如果您还是很懵。您可以看一下代码：

#include <iostream>
#include <string>
#include <algorithm>
#include <cstring>

using namespace std;

char stra[100001],strb[100001];
int x[100001],y[100001];
int cans[10000001];

string mul(char numa[],char numb[])
{
    string pns;
    int la=strlen(numa);
    int lb=strlen(numb);
    reverse(stra,stra+la);
    reverse(strb,strb+lb);
    for(int i=0;i<la;i++)
        x[i]=stra[i]-'0';
    for(int i=0;i<lb;i++)
        y[i]=strb[i]-'0';
    for(int i=0;i<la;i++)
    {
        for(int j=0;j<lb;j++)
        {
            cans[i+j]=cans[i+j]+x[i]*y[j];
        }
    }
    for(int i=0;i<la+lb-1;i++)
    {
        cans[i+1]=cans[i+1]+cans[i]/10;
        cans[i]=cans[i]%10;
        pns=char(cans[i]+'0')+pns;
    }
    if(cans[la+lb-1]>0)
    {
        pns=char(cans[la+lb-1]+'0')+pns;
    }
    return pns;
}

int main()
{
    cin>>stra>>strb;
    cout<<mul(stra,strb);
    return 0;
}

您有任何疑问均可在讨论里与我讨论。我将尽快答复

高精度大概就这样了。
一般NOI下的高精度也就这样。
好吧，写篇文章就到这里了。hh

高精度计算