Term end = 0.300000 bin: 33 33 33 33 33 33 d3 3f
Round 1 a = 0.100000 bin: 9a 99 99 99 99 99 b9 3f
Round 2 a = 0.200000 bin: 9a 99 99 99 99 99 c9 3f
Round 3 a = 0.300000 bin: 34 33 33 33 33 33 d3 3f
end
的16进制表示是0x3fd3333333333333
,而当a
加到0.3的时候,它的16进制表示是0x3fd3333333333334
。这两者不一致,因此不会进入循环终止条件。
我们上面提到,要想将一个浮点数存储在寄存器中,需要首先将其转化为二进制的小数。那么,0.1转化为二进制小数为0.0001100110011001101...,而0.3转化为二进制小数为0.01001100110011001101...。我们震惊地发现,十进制小数转化成的二进制小数居然不整。
这下就能解释为什么这个程序停不下来了。由于转化的二进制小数不整,因此存储在寄存器中时,发生了截断,产生了一定的误差。那么,在进一步计算时,误差就会累积,从而几乎没有可能真正到达0.3。这就是浮点数算术的精度问题。
这种精度问题在我们实际的生活中会遇到吗?下面,我就介绍一个在Dark Souls速通中被发现的一个Meme Roll Glitch(视频讲解可以看B站搬运的视频《黑暗之魂》中“最疯狂”的skip是如何诞生的的24:45秒开始)。
在Dark Souls中,从高空坠落会受到伤害,当高度高于一定阈值时,人物会死亡。在游戏速通中,玩家希望通过一些地方的跳跃到达后期才能去的地区,从而绕过很多步骤,节省大量的时间。但是,这些跳跃往往高度都非常高,会造成角色的死亡,直接跳显然是不行的。在Meme Roll Glitch发现之后,这个问题终于得到了解决。
提出这个Glitch的玩家发现,当角色的负重在25%与25.000088%之间时,角色可以在高空坠落的过程中不断地翻滚,从而利用翻滚的无敌帧避开坠落的伤害。但是,负重在游戏中的最小计量单位是0.1%,理论上不可能使角色的负重在这个范围内。这就需要浮点数算术的精度问题了。由于浮点数本身采用二进制小数进行存储,所以不可能精确等于其十进制数值。因此通过仔细地调整装备与耐力等级,不断利用浮点数算术的精度误差,最终能使角色处在这一负重范围内,最终实现无伤害坠落。
在一些现代编程语言中,编译器会很聪明地阻止我们干一些事。例如,如果我们想用Rust语言对浮点数的数组进行排序:
#![allow(unused)]
fn main() {
let mut s = [1.0, -3.5, 4.7];
s.sort();
会发现编译不通过,提示"the trait Ord
is not implemented for {float}
"。这是为什么呢?要解释这一问题,我们不妨先了解一下IEEE754标准里几个特殊的常数(可以参考codes/2-special-numbers.c)。
之前我们提到,存储浮点数时会存储其符号信息。但是,其余数字的存储并不一定会像整数一样使用补码。事实上,在IEEE754标准里,有两个零值:+0.0
与-0.0
。
零值存储的值是不同的:+0.0
存储的值为0x00000000
,-0.0
存储的值为0x00000080
。
但是,在比较运算中,+0.0
与-0.0
是相等的。
INFINITY
代表无穷大, 有+INFINITY
与-INFINITY
两个值。
一般可以通过1.0/0.0
以及1.0/-0.0
得到无穷大值。
在比较运算中,+INFINITY
大于所有除了其本身的值;-INFINITY
小于所有除了其本身的值。
代表非数值。有+NAN
和-NAN
两个值。
可以通过对-1.0
开方等操作得到。
其与任何数都不相等。也就是说,NAN != NAN
,-NAN != -NAN
。也无法进行比较,也就是说,NAN
于任何数进行小于、大于的比较,返回结果都是false
。
介绍了这些特殊的常数,那么,我们就可以解答为什么f32
不满足Eq
的trait了。
Ord
trait,就是全序关系。集合\(X\)上可以建立全序关系,意思就是说:
对于\(X\)中的元素\(a\), \(b\), \(c\)有:
如果\(a\leq b\)且\(b\leq a\),则\(a=b\)
如果\(a\leq b\)且\(b\leq c\),则\(a\leq c\)
对于\(X\)中的任意元素\(a\)和\(b\),都有\(a\leq b\)或\(b\leq a\)
对于我们最常接触的整数来说,这些性质是非常显然的,因此整数可以建立全序关系。
但是,对于我们刚刚提到的IEEE754定义的浮点数类型来说,由于NAN
与任何数都不相等,因此浮点数不可以建立全序关系,从而不满足Ord
trait。
直观地,我们也可以看出来,NAN
这样特殊的数,无法进行比较,从而如果出现在数组中,对其排序是没有意义的。