网络赛前10奖励计蒜客的本子或鼠标垫(外校也可以来现场领取)
Xidian Online Judge WebBoard
[ New Thread ]
MainBoard >> 关于精度问题【科普向】
mathlover @ 2015-05-19 08:14:52
[ Quote ] [ Edit ] [ Delete ] 1#
0.精度问题是什么?
当题目中的运算最高需要P位精确数字,然而你的代码,由于算法原因,或者编译器原因,甚至是系统原因达不到这个P位精确数字的要求,在一些特殊的数据中(有可能是出题人专门出的,有可能是无意出的),你的代码也许就会和标准答案相差一个丢丢,通常表现为最后一位不同。
mathlover @ 2015-05-19 08:15:00
[ Quote ] [ Edit ] [ Delete ] 2#
1.举几个常见的栗子
我们知道,int是表示32位整数,其中默认为signed,有符号,能精确地表示-2147483648~2147483647闭区间中所有整数。如果还不够,我们就要用long long这种64位的整数,默认也是signed有符号型,能精确表示 -9223372036854775808~9223372036854775807之间的任意整数。

现在问题来了,当我们在把long long和一个double相乘,会有什么后果?当我们在把int和一个float相乘,会有什么后果?

首先我们来科普一下浮点数在计算机的存储方式(整数就不用了吧~)
float=1位的符号位+23位精度位+8位的指数位
double=1位的符号位+52位精度位+11位的指数位
也就是说,float能精确地存储23个0/1的数字,double能精确地存储52个0/1的数字。
23个精度位相当于7个十进制数字
52个精度位相当于17个十进制数字
看上去很多?
看上去很精确?
我们回过头来看看整型,int有31个精度位,long long有63个精度位

所以说,一个int和一个float相乘会丢失8个精度位,也就是3位十进制小数,long long和double相乘会丢失11个精度位,也就是4位十进制的小数。

或许大家觉得反正丢的都是最后几位。。。我只要保留到小数点后两三位不就行了么~?

理想很丰满,然而现实很骨感~

如果小数点前面有很多数字?那么小数点后的第一位正好是你即将丢失的那一位?
Game over~!

有一种极端的情况。
我们知道,如果在编程中,如果要输出的值精确到小数点后两位,无论是%.2f的printf型输出,还是setprecision(2)的流输出,还是floor(x*100+0.5)的数学公式输出,对于小数点后的第三位,编译器都是采取四舍五入的方式。然而四与五之间虽然隔了一堵墙,但是也许这堵墙很薄很薄?你这样一刀切真的准确吗?

估计大家看不懂我上面的那个比喻,没关系,你看看下面的例子就知道了
http://acm.xidian.edu.cn/problem.php?id=1029
我们需要输出的是pow(10,n*log10(2)-floor(n*log10(2)))的整数部分,然而当n=3的时候,我们都知道这个答案毫无疑问应该是8
于是我们就很开心很幸福地写下了printf("%d\n",(int)pow(10,n*log10(2)-floor(n*log10(2))));
或者printf("%.0f\n",floor(pow(10,n*log10(2)-floor(n*log10(2)))));
然而很不幸,电脑很弱智地输出了7
我们感觉被骗了!
于是你就打破砂锅问到底
printf("%.20f\n",pow(10,n*log10(2)-floor(n*log10(2))));
卧槽7.99999999999999910000
也就是说电脑正好在第17位有效数字上产生了精度误差了!这正好差了一点点!!!
printf("%.2f\n",1.045*9.87654321/9.87654321);
本来应该是1.045然后四舍五入保留两位小数输出是1.05
然而电脑输出了1.04
printf("%.20f\n",1.045*9.87654321/9.87654321);
输出1.04499999999999990000
(让我们在这里为艾神默哀一下,你懂得!)
mathlover @ 2015-05-19 08:15:11
[ Quote ] [ Edit ] [ Delete ] 3#
2.作为acmer,浮点数精度问题会有什么后果?
浮点数精度问题是一个比较隐蔽的问题,通常出现在涉及大量浮点数运算的题目,最典型就是计算几何。
然而有可能连出题人都没预料这一点,所以经常会出现一种情况就是,你取的精度误差EPS和出题人的不一样,就会Wrong Answer,很残酷吧~~~
mathlover @ 2015-05-19 08:15:19
[ Quote ] [ Edit ] [ Delete ] 4#
3.怎么解决这种问题?
方法一:从出题人的角度,要么在数据上尽可能避免会出现浮点数精度问题的数据,然而这时很难避免的,甚至出题人也很难让自己的标程代码完全正确,至于人脑验证数据的正确性。。。。呵呵。。。
方法二:出题人另外一种解决方法就是写一个special judge。当绝对精度和相对精度在一个接受范围内,就判成Accepted或Yes

方法三:从参赛选手的角度,要避免太多的浮点数的运算,尤其是一些复杂的函数,例如三角函数啊,对数函数啊,指数函数,别以为2的3次方=8是一个很简单的式子,别以为sin(PI/2)=1是一个很简单的东西,你试试手算一下1.7的3.5次方?试一下手算一下sin(1.23456)?。编译器内部为了适应浮点参数,对这些函数的实现一律都是泰勒展开式。。。然后当精度足够(满足double的范围)时才停止运算,可想而知中间要经过多少次的乘法除法和加法减法?造成的精度误差却是像多米诺效应一样越滚越大~

方法四:从裁判的角度,虽然说Online Judge上的裁判就是电脑,如果没有special judge,那么电脑也就是一个无情的机器,那在现场赛中,往往需要人工干预评判结果,也就是所谓的半自动判题方式(参考校赛)。对于一些涉及浮点数运算太多的题目,裁判还是应该拿选手的输出和标准输出进行比对一下,如果仅仅是一丢丢的精度误差,还是手下留情,给一个Accepted吧,毕竟交题容易,AC不易。大家都是这样走过来,做人留一线,日后好相见啊~
mathlover @ 2015-05-19 08:15:36
[ Quote ] [ Edit ] [ Delete ] 5#
沙发自抢~板凳随意~
14020310076 @ 2015-05-19 08:38:51
[ Quote ] [ Edit ] [ Delete ] 6#
板凳!!!前排膜拜~Orz
13121144 @ 2015-05-19 11:58:01
[ Quote ] [ Edit ] [ Delete ] 7#
前排膜拜数一!Orz Orz
13060410021 @ 2015-05-19 23:54:59
[ Quote ] [ Edit ] [ Delete ] 8#
13130120146 @ 2015-05-20 07:52:30
[ Quote ] [ Edit ] [ Delete ] 9#
谢谢数一女神
02129007 @ 2015-05-21 20:06:59
[ Quote ] [ Edit ] [ Delete ] 10#
方法五:用Java,完美解决精度问题。
adminlight @ 2015-05-22 15:59:25
[ Quote ] [ Edit ] [ Delete ] 11#
然后你就会一直TLE到比赛结束
@02129007
xry111 @ 2015-05-23 23:44:13
[ Quote ] [ Edit ] [ Delete ] 12#
@02129007
完美解决精度问题物理上就是不可能的,比如用BigDecimal算10/3就会抛异常,你要手工指定截断位数,这就引入了精度问题
[Top] [Previous Page] [Next Page]
Anything about the Problems, Please Contact Admin:admin
All Copyright Reserved 2010-2014 Xidian ACM Online Judge TEAM
GPL2.0 2003-2014 HUSTOJ Project TEAM