精度误差 - 洛谷保存站

## 引子

这是一段非常普通的代码。

```
#include<bits/stdc++.h>
using namespace std;
int main(){
    double c=3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342117068;
    printf("%.15lf\n",c);
}
```

它输出 $3.14159265358979323$，看上去人畜无害。但是当我们把输出位数改为 $25$（即 `printf("%.25lf\n",c);`）时，有一件神秘的事情发生了：

它的输出是 $3.141592653589793\color{red}{1159979635}$。

但是我们想要的是 $3.141592653589793\color{blue}{2384626433}$。

而如果 $c$ 是 float 类型，输出 $3.1415927410125732421875000$，在小数点后第 $7$ 位就出现了错乱。

如果我们将 $c$ 的值换成一个超级大的整数，例如 $11451419198102085$，会发生什么呢？

```
#include<bits/stdc++.h>
using namespace std;
int main(){
    double c=11451419198102085;
    printf("%.25lf\n",c);
}
```

输出的结果是：$11451419198102084.0000000000000000000000000$。

如果把 $c$ 设为 $114514191981020851415$，那么就全乱套了，输出的是 $3833727538763541504.0000000000000000000000000$。

种种迹象表明，double 类型最多只能保留 $16$ 位有效数字，再往上就全部乱套了。

那么这个的原理是什么呢？double 是否还能稳定使用呢？

了解这个的前提是我们了解计算机存储浮点数的方法。

## 计算机存储浮点数的机理

在计算机中，double 类型基于 IEEE 754 标准，使用 $64$ 位二进制表示浮点数。也就是我们所谓的双精度浮点数。

单精度浮点数 float 则更加寒酸，只有 $32$ 位用来存储浮点数。

浮点数在计算机中的存储也是基于二进制进行的。具体来说，是如下图：

![](https://cdn.luogu.com.cn/upload/image_hosting/kgydx69x.png)

我们以单精度浮点数的存储为例。

首先，假如我们有这样一个单精度浮点数 $20.5$。

根据二进制存储小数，$(20.5)_{10}=(10100.1)_2$。

二进制存储小数的原理：

|二进制位    |该位数字|
|:------:|:--:|
|$2^4$   |$1$ |
|$2^3$   |$0$ |
|$2^2$   |  $1$  |
|$2^1$   |  $0$  |
|$2^0$   |   $0$ |
|$2^{-1}$|  $1$  |

紧接着，我们对这个二进制小数 $10100.1$ 进行二进制科学计数法表示。

$(10100.1)_2=(1.01001)_2\times ((10)_2)^4$

但是还有一种可能：这个数太大了，需要乘 $((10)_2)^{-x}$ 才能满足条件。

所以这 $8$ 位指数位，其实只能存储 $[-127,128]$ 的指数。在实际存储时，会将这个数加上 $127$ 偏移一下然后存进去。

然后剩下的小数部分 $01001$ 就直接扔进尾数位去就可以了。但是 $01001$ 远没有 $23$ 位，所以缺失的位数要补 $0$。

![](https://cdn.luogu.com.cn/upload/image_hosting/aykleh6d.png)

当然了，这只是理想状态。实际情况远比这个要残酷的多。例如小数 $0.6$，如果转化为二进制就是无限小数 $(0.1001\ 1001\ 1001\ 1001\cdots)_2$。

从二进制小数转十进制浮点数时，首先把尾数位提取出来，然后加入整数位 $1$（二进制科学计数法表示整数位一定是 $1$），然后提取指数位，恢复原先的小数点位置。然后转化为十进制，加上正负号。

但是你是否注意到上面 $0.6$ 的例子？并不是所有的小数都可以正好被存储，有的无限小数只能存储一部分，然后就引发了误差。例如，如果某种非常低级的 lowfloat 类型，尾数位只有四位，那么它存储 $0.6$，回来之后就会变成 $0.5625$。这个误差是存在的。

## 累积误差

显然我们使用 double 并不只是为了存储浮点数，而是为了计算与比较。

假设我们现在有两个浮点数 $114514.191981$ 与 $2085.143159$，我要把它们相乘。

正确答案是 $238778484.017594807979$。

但是假设由于计算机误差，导致这两个浮点数存储为了 $114514.\color{blue}{182736}$ 和 $2085.143\color{blue}{021}$。那么它们相乘就是 $2387784\color{blue}{48.937489085456}$。

前面勉强还能接受的误差直接溢到了整数位，显然非常烦人。

这就是累积误差。在存在小误差时，如果继续计算，小误差相乘相加可能就会对答案造成比较大的影响。

这就是你使用浮点数类型时，造成误差的最直接原因。

## 各种浮点数类型的极限是多少

相信比起了解计算机存储浮点数的原理，你更想要知道 float 和 double 等基本类型精度的极限是多少。

### float

float 既然作为单精度浮点数，它的精度极限自然不大。

```
#include<bits/stdc++.h>
using namespace std;
const double eps=1e-25;
int main(){
    float a=0.114514;
    printf("%.25lf\n",a);
}
```

你可以把这段代码的 $a$ 改变并且去运行。下面我给出几组测试数据（蓝色为产生不准确的位数）：

| $a$  | 输出  |
|:-:|:-:|
|  $0.114514$ |  $0.114514000\color{blue}{7138252258300781}$ |
|  $0.5119597470941000038$ |  $0.5119597\color{blue}{315788269042968750}$ |
| $3.14159265358979323846264338327950288419765939$  | $3.141592\color{blue}{7410125732421875000}$  |
|  $9125776.23424729324353$（$10^7$ 量级） | $9125776.\color{blue}{0000000000000000000000000}$  |
| $912524776.23424729324353$（$10^9$ 量级）  | $912524\color{blue}{800.0000000000000000000000000}$  |
| $912524776912524776.23424729324353$（$10^{18}$ 量级） |  $9125247\color{blue}{63346239488.0000000000000000000000000}$ |

在数据范围大的情况下，float 产生的误差甚至能溢到整数位，这是不可接受的。所以在算法竞赛中，**不到卡空间的时候千万不要用 float！**

### double

```
#include<bits/stdc++.h>
using namespace std;
const double eps=1e-25;
int main(){
    double a=0.114514;
    printf("%.25lf\n",a);
}
```

|  $a$ | 输出  |
|:-:|:-:|
|  $0.114514$ | $0.11451400000000000\color{blue}{46753712}$  |
|  $0.11451423573845279312032329572985104623885$ |  $0.11451423573845279\color{blue}{09136551}$ |
|$738452793.12032323353856353549572985104623885$（$10^9$ 量级） | $738452793.120323\color{blue}{1811523437500000000}$|
| $114514235738452793.12032323353856353549572985104623885$（$10^{18}$ 量级）  | $114514235738452\color{blue}{800.0000000000000000000000000}$  |

在 $10^9$ 量级的数据下，double 还可以跑到 $10^{-6}$ 的精度，还是可以的。

### long double

首先要知道的是，long double 在不同环境下的二进制位数是不同的。有的地方是 $80$ 位，有的地方是 $128$ 位。

[U498224 float、double 与 long double](https://www.luogu.com.cn/problem/U498224) 是在洛谷评测平台做的一个 long double 测试。

- [long double 记录](https://www.luogu.com.cn/record/232054302)
- [double 记录](https://www.luogu.com.cn/record/232053641)

评测数据在题目附件中。

可以看出，在相同数据下，long double 比 double 可以多存储 $4$ 位。

## 避免精度误差的方式

### 浮点数比较：eps

很多选手在不得不使用浮点数比较时，都会把简单的 `a>b` 改为 `a-b>eps`。这个 $eps$ 其实是单词 epsilon 的缩写，是一个极小常数。它的目的是比较两个数近似相等而非完全相等。

例如：

```
#include<bits/stdc++.h>
using namespace std;
int main(){
	double a=1.0*522440.335527/36672.100382,b=1.0*2475081569.2203151584/173735513.1060599744;
	printf("%.25lf\n%.25lf\n",a,b);
	return 0;
}
//*4737.5392
```

输出的答案是：

$$14.24626160173341\color{red}{91553800338}$$
$$14.24626160173341\color{blue}{73790231944}$$

但是后者其实是前者的分母分子同乘 $4737.5392$ 得到的。理论来说，这两个数应该相等。

诶！那么如果我们设一个 $eps=10^{-10}$，然后比较 $|a-b|$ 与 $eps$ 的相对大小。那么只要 $a$ 和 $b$ 的误差在 $eps$ 之内，那么我们就可以认定它们是相等的！

这就是 $eps$ 法，一定程度上避免了比较时精度误差造成的问题。

### 分数类

```
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=100005;
struct frac{
	ll a,b;
	friend bool operator <(frac f,frac g){
		if(f.a*g.b>=f.b*g.a)return 0;
		else return 1;
	} 
	friend bool operator >(frac f,frac g){
		if(f.a*g.b<=f.b*g.a)return 0;
		else return 1;
	} 
	friend bool operator ==(frac f,frac g){
		if(f.a==g.a&&f.b==g.b)return 1;
		else return 0;
	}
}a[N];
frac yf(frac a){
	ll t=__gcd(a.a,a.b);
	frac nf;
	nf.a=a.a/t;
	nf.b=a.b/t;
	return nf;
}
int n;
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%lld%lld",&a[i].a,&a[i].b);
		a[i]=yf(a[i]);
	}
	int q;scanf("%d",&q);
	for(int x,y;q;q--){
		scanf("%d%d",&x,&y);
		if(a[x]==a[y])printf("equal\n");
		else if(a[x]<a[y])printf("small\n");
		else printf("big\n");
	}
	return 0;
}
```

这是一个可以比较两个分数大小的代码。

基理是通分，然后比较分子。

优点是不会出现精度误差。缺点也很明显：long long 也有限制。它的分子分母最大只能是 $10^9$（不然通分就炸了）。

### 计算可能误差

以 [AT_abc418_e](https://www.luogu.com.cn/problem/AT_abc418_e) 为例。

假若我们采用计算斜率，排序的方法。那么会有多大的误差呢？

注意到 $\dfrac{20000000}{19999999}=1.00000005000000\color{blue}25000001250000063$，$\dfrac{19999999}{19999998}=1.00000005000000\color{blue}500000050000005$。也就是说，你至少需要把 $eps$ 设到 $10^{-14}$，才能保证这两个值不被判断为相等。实际上，在日常使用中，一般会开大一点。

正在渲染内容...