房地产行业网站开发,创建网站向导和模板,网站推广托管,wordpress+积分+文章计算几何的精度问题说到底其实是浮点数的精度问题#xff0c;但我觉得“计算几何”比“浮点数”更能吸引眼球#xff0c;所以选了这个标题。
1.浮点数为啥会有精度问题#xff1a;
浮点数(以C/C为准)#xff0c;一般用的较多的是float, double。 占字节数 数值范围 十进…计算几何的精度问题说到底其实是浮点数的精度问题但我觉得“计算几何”比“浮点数”更能吸引眼球所以选了这个标题。
1.浮点数为啥会有精度问题
浮点数(以C/C为准)一般用的较多的是float, double。 占字节数 数值范围 十进制精度位数 float 4 -3.4e-383.4e38 6~7 double 8 -1.7e-3081.7e308 14~15
如果内存不是很紧张或者精度要求不是很低一般选用double。14位的精度(是有效数字位不是小数点后的位数)通常够用了。注意问题来了数据精度位数达到了14位但有些浮点运算的结果精度并达不到这么高可能准确的结果只有10~12位左右。那低几位呢自然就是不可预料的数字了。这给我们带来这样的问题即使是理论上相同的值由于是经过不同的运算过程得到的他们在低几位有可能(一般来说都是)是不同的。这种现象看似没太大的影响却会一种运算产生致命的影响: 。恩就是判断相等。注意C/C中浮点数的需要完全一样才能返回true。来看下面这个例子:
#includestdio.h
#includemath.h
int main()
{ double a asin(sqrt(2.0) / 2) * 4.0; double b acos(-1.0); printf( a %.20lf\n, a); printf( b %.20lf\n, b); printf( a - b %.20lf\n, a - b); printf(a b %d\n, a b); return 0;
}
输出 a 3.14159265358979360000 b 3.14159265358979310000 a - b 0.00000000000000044409
a b 0
我们解决的办法是引进eps来辅助判断浮点数的相等。
2. eps eps缩写自epsilon表示一个小量但这个小量又要确保远大于浮点运算结果的不确定量。eps最常见的取值是1e-8左右。引入eps后我们判断两浮点数a、b相等的方式如下:
定义三出口函数如下: int sgn(double a){return a -eps ? -1 : a eps ? 0 : 1;}
则各种判断大小的运算都应做如下修正: 传统意义 修正写法1 修正写法2 a b sgn(a - b) 0 fabs(a – b) eps a ! b sgn(a - b) ! 0 fabs(a – b) eps a b sgn(a - b) 0 a – b -eps a b sgn(a - b) 0 a – b eps a b sgn(a - b) 0 a – b eps a b sgn(a - b) 0 a – b -eps
这样我们才能把相差非常近的浮点数判为相等;同时把确实相差较大(差值大于eps)的数判为不相等。
PS: 养成好习惯尽量不要再对浮点数做判断。例如我的修正写法2里就没有出现。
3. eps带来的函数越界
如果sqrt(a), asin(a), acos(a) 中的a是你自己算出来并传进来的那就得小心了。
如果a本来应该是0的由于浮点误差可能实际是一个绝对值很小的负数(比如1e-12),这样sqrt(a)应得0的直接因a不在定义域而出错。
类似地如果a本来应该是±1,则asin(a)、acos(a)也有可能出错。
因此对于此种函数必需事先对a进行校正。
4. 输出陷阱I
这一节和下一节一样都是因为题目要求输出浮点数导致的问题。而且都和四舍五入有关。
说到四舍五入就再扯一下相关内容,据我所知有三种常见的方法:
1. printf(“%.3lf”, a); //保留a的三位小数按照第四位四舍五入
2. (int)a; //将a靠进0取整
3. ceil(a); floor(a); //顾名思义向上取证、向下取整。需要注意的是这两个函数都返回double而非int
其中第一种很常见于输出(nonsense…)。
现在考虑一种情况,题目要求输出保留两位小数。有个case的正确答案的精确值是0.005,按理应该输出0.01,但你的结果可能是0.005000000001(恭喜)也有可能是0.004999999999(悲剧),如果按照printf(“%.2lf”, a)输出那你的遭遇将和括号里的字相同。
解决办法是如果a为正则输出aeps, 否则输出a-eps
典型案例: POJ2826
5. 输出陷阱II
ICPC题目输出有个不成文的规定(有时也成文)不要输出: -0.000
那我们首先要弄清什么时候按printf(“%.3lf\n”, a)输出会出现这个结果。
直接给出结果好了a∈(-0.000499999……, -0.000……1)
所以如果你发现a落在这个范围内请直接输出0.000。更保险的做法是用sprintf直接判断输出结果是不是-0.000再予处理。
典型案例:UVA746
6. 范围越界
这个严格来说不属于精度范畴了不过凑数还是可以的。请注意虽然double可以表示的数的范围很大却不是不穷大上面说过最大是1e308。所以有些时候你得小心了比如做连乘的时候必要的时候要换成对数的和。
典型案例:HDU3558
7. 关于setT
有时候我们可能会有这种需求对浮点数进行 插入、查询是否插入过 的操作。手写hash表是一个方法(hash函数一样要小心设计)但set不是更方便吗。但set好像是按来判重的呀貌似行不通呢。经观察,set不是通过来判断相等的是通过来进行的具体说来只要ab 和 ba 都不成立就认为a和b相等可以发现
如果将小于定义成: bool operator (const Dat dat)const{return val dat.val - eps;}就可以解决问题了。 (基本类型不能重载运算符所以封装了下)
8. 输入值波动过大
这种情况不常见不过可以帮助你更熟悉eps。假如一道题输入说给一个浮点数a, 1e-20 a 1e20。那你还敢用1e-8做eps么合理的做法是把eps按照输入规模缩放到合适大小。
典型案例: HUSTOJ 1361
9. 一些建议
容易产生较大浮点误差的函数有asin、 acos。欢迎尽量使用atan2。
另外如果数据明确说明是整数而且范围不大的话使用int或者long long代替double都是极佳选择因为就不存在浮点误差了(尽管我几乎从来都只用double --!)
转自https://blog.csdn.net/entalent/article/details/47620341
