12.高精度计算

时间：2022-04-12 01:15:15

一、引入

1.简介

高精度计算（Arbitrary-Precision Arithmetic），也被称作大整数（bignum）计算，运用了一些算法结构来支持更大整数间的运算（数字大小超过语言内建整型）。

2.表示

在平常的实现中，高精度数字利用字符串表示，每一个字符表示数字的一个十进制位。因此可以说，高精度数值计算实际上是一种特别的字符串处理。

读入字符串时，数字最高位在字符串首（下标小的位置）。但是根据我们日常生活中计算的习惯，下标最小的位置存放的是数字的最低位，即存储反转的字符串。这么做还有一个好处就是，数字的长度可能发生变化，但同样权值位始终保持对齐。

ll la=a.size(),lb=b.size();  
for(ll i=0;i<la;i++)
    na[la-1-i]=a[i]-'0';  
for(ll i=0;i<lb;i++)
	nb[lb-1-i]=b[i]-'0';

3.时间复杂度说明

对于乘法和除法运算，由于时间复杂度上的需求，我们将会分成单精度与高精度运算，高精度与高精度运算。

  • 单精度与高精度的运算时间复杂度为： O ( n ) O(n) O(n)
  • 高精度与高精度的运算时间复杂度为： O ( n 2 ) O(n^2) O(n2)

二、加减法

1.加法

高精度加法的原理其实就是竖式加法。也就是从最低位开始，将两个加数对应位置上的数码相加，并判断是否达到或超过 10 10 10。如果达到，那么处理进位：将更高一位的结果上增加 1 1 1，当前位的结果减少 10 10 10。

限制 a , b a,b a,b两个字符串都代表非负整数，且无前导零。

string add(string a,string b)
{  
    string ans;
	memset(na,0,sizeof(na));
	memset(nb,0,sizeof(nb));   
    ll la=a.size(),lb=b.size();  
    for(ll i=0;i<la;i++)
		na[la-1-i]=a[i]-'0';  
    for(ll i=0;i<lb;i++)
		nb[lb-1-i]=b[i]-'0';  
    ll lmax=la>lb?la:lb;  
    for(ll i=0;i<lmax;i++)
	{
		na[i]+=nb[i];
		na[i+1]+=na[i]/10;
		na[i]%=10;
	}
    if(na[lmax])
		lmax++;  
    for(ll i=lmax-1;i>=0;i--)
		ans+=na[i]+'0';  
    return ans;
}

2.减法

高精度减法的原理其实就是竖式减法。也就是从个位起逐位相减，遇到负的情况则向上一位借 1 1 1。整体思路与加法完全一致。由于减法可能会导致多位为 0 0 0，所以需要人为去除前导 0 0 0。

限制 a , b a,b a,b两个字符串都代表非负整数，且无前导零。

string sub(string a,string b)
{
	memset(na,0,sizeof(na));
	memset(nb,0,sizeof(nb));
	bool flag=false;
	if(a.size()<b.size() || (a.size()==b.size() && a<b))
	{
		swap(a,b);
		flag=true;
	}
    string ans;
    ll la=a.size(),lb=b.size();  
    for(ll i=0;i<la;i++)
		na[la-1-i]=a[i]-'0';  
    for(ll i=0;i<lb;i++)
		nb[lb-1-i]=b[i]-'0';  
    int lmax=la>lb?la:lb;  
    for(int i=0;i<lmax;i++)  
    {  
        na[i]-=nb[i];  
        if(na[i]<0)
        {
        	na[i]+=10;
			na[i+1]--;
		}
    }  
    while(!na[--lmax] && lmax>0)
		;
	lmax++;  
    for(ll i=lmax-1;i>=0;i--)
		ans+=na[i]+'0';
	if(flag)
		cout<<"-";  
    return ans;
}

三、乘法

1.单精度乘高精度

先考虑一个简单的情况：乘数中的一个是普通的整型数。即 a , b a,b a,b中 b b b为

一个直观的思路是直接将 a a a每一位上的数字乘以 b b b。从数值上来说，这个方法是正确的，但它并不符合十进制表示法，因此需要将它重新整理成正常的样子。

重整的方式，也是从个位开始逐位向上处理进位。但是这里的进位可能非常大，甚至远大于 9 9 9，因为每一位被乘上之后都可能达到 9 b 9b 9b 的数量级。所以这里的进位不能再简单地进行 − 10 -10 −10运算，而是要通过除以 10 10 10的商以及余数计算。

单精度乘高精度指一个整型变量乘以一个超过c++整数表示范围的数。

string mul(string a,ll b)
{
	string ans;
	ll La=a.size();
	memset(na,0,sizeof(na));
	for(ll i=La-1;i>=0;i--)
		na[La-i-1]=a[i]-'0';
	ll w=0;
	for(ll i=0;i<La;i++)
		na[i]=na[i]*b+w,w=na[i]/10,na[i]=na[i]%10;
	while(w)
		na[La++]=w%10,w/=10;
	La--;
	while(La>=0)
		ans+=na[La--]+'0';  
	return ans;
}

2.高精度乘高精度

如果两个数都是高精度，直接仿照竖式乘法的模式即可。

高精度乘高精度指两个超过c++整数表示范围的数。

string mul(string a,string b)
{
	memset(na,0,sizeof(na));
	memset(nb,0,sizeof(nb));
	memset(nc,0,sizeof(nc));
    string s;  
    ll La=a.size(),Lb=b.size();
    for(ll i=La-1;i>=0;i--)
		na[La-i]=a[i]-'0';
    for(ll i=Lb-1;i>=0;i--)
		nb[Lb-i]=b[i]-'0';  
    for(ll i=1;i<=La;i++)  
        for(ll j=1;j<=Lb;j++)  
        	nc[i+j-1]+=na[i]*nb[j];
    for(ll i=1;i<=La+Lb;i++)  
        nc[i+1]+=nc[i]/10,nc[i]%=10;
    if(nc[La+Lb])
		s+=nc[La+Lb]+'0';
    for(ll i=La+Lb-1;i>=1;i--)  
        s+=nc[i]+'0';
    return s;  
}

四、除法

除法的原理与乘法相同，这里不再赘述。

1.多精度除以单精度

string div(string a,ll b)//高精度a除以单精度b  
{
	string r,ans;
	ll d=0;
	if(a=="0")
		return a;
	for(ll i=0;i<a.size();i++)  
	{
		r+=(d*10+a[i]-'0')/b+'0';//求出商  
		d=(d*10+(a[i]-'0'))%b;//求出余数  
	}  
	ll p=0;  
	for(ll i=0;i<r.size();i++)
	{
		if(r[i]!='0')
		{
			p=i;
			break;
		}
	}
    return r.substr(p);  
}

2.多精度除以多精度

ll sub(ll *a,ll *b,ll La,ll Lb)  
{  
    if(La<Lb)
		return -1;
    if(La==Lb)  
    {  
        for(ll i=La-1;i>=0;i--)
        {
        	if(a[i]>b[i])
				break;  
            else if(a[i]<b[i])
				return -1;
		}
    }  
    for(ll i=0;i<La;i++)
    {  
        a[i]-=b[i];  
        if(a[i]<0)
		{
			a[i]+=10;
			a[i+1]--;
		}
    }  
    for(ll i=La-1;i>=0;i--)  
        if(a[i])
			return i+1;
    return 0;
  
}  
void div(string n1,string n2)
{
    string s,v;
    ll a[maxn],b[maxn],r[maxn],La=n1.size(),Lb=n2.size(),i,tp=La;
    memset(a,0,sizeof(a));
    memset(b,0,sizeof(b));
    memset(r,0,sizeof(r));
    for(i=La-1;i>=0;i--)
		a[La-1-i]=n1[i]-'0';  
    for(i=Lb-1;i>=0;i--)
		b[Lb-1-i]=n2[i]-'0';  
    if(La<Lb || (La==Lb && n1<n2))
    {
    	cout<<"0 "<<n1<<endl;
    	return;
	}
    ll t=La-Lb;
    for(ll i=La-1;i>=0;i--)
    {
     	if(i>=t)
			b[i]=b[i-t];  
        else
			b[i]=0;
	}
    Lb=La;  
    for(ll j=0;j<=t;j++)  
    {  
        int temp;  
        while((temp=sub(a,b+j,La,Lb-j))>=0)
        {  
            La=temp;  
            r[t-j]++;  
        }  
    }  
    for(i=0;i<maxn-10;i++)
	{
	 	r[i+1]+=r[i]/10;
		r[i]%=10;
	}
    while(!r[i])
	 	i--;
    while(i>=0)
	 	s+=r[i--]+'0';  
    i=tp;  
    while(!a[i])
	 	i--;
    while(i>=0)
	 	v+=a[i--]+'0';  
    if(v.empty())
	 	v="0";
	if(v!="0")
		cout<<s<<" "<<v<<endl;
	else
		cout<<s<<endl;
}

五、未来

大家不难发现，高精度计算有时会达到 O ( n 2 ) O(n^2) O(n2)的时间复杂度，这样的复杂度在很多时候都是不可接受的，尤其是高精度仅仅是一个工具的情况下。故而还有一些更好的方式来实现高精度计算：

  • 压位高精度计算
  • K a r a t s u b a Karatsuba Karatsuba乘法： O ( n l o g 2 3 ) O(n^{log_23}) O(nlog2​3)
  • 快速傅里叶变换： O ( n l o g n ) O(nlogn) O(nlogn)

六、作业

P1601 A+B Problem（高精）

P2142 高精度减法

P1303 A*B Problem

P1480 A/B Problem

P1009 [NOIP1998 普及组] 阶乘之和

标签：

相关文章