高精度计算

高精度计算

smallfang

2020 年 08 月 25 日

576 次浏览

暂无评论

481字数

算法笔记

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

## 概念

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

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

## 实现

### 四则运算之加法:

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

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

代码：

```cpp
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";
}
```

### 四则运算之减法：

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

```cpp
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]是正确的。

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

```cpp
#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

最后修改：2020 年 08 月 26 日