IEEE浮点数的设计缺陷

在生物化学中,“信息”是研究物质的2个基本视角之一,另外一个是“能量”。因为信息和能量都是抽象出来的东西,以它们为视角研究现实世界的成本非常低,比如计算机专业的学生做实验只需要一台电脑就可以了(搞深度学习的除外),不像其他理工科类,他们做一次实验得花好多钱准备设备和材料,实验做得少就会大大降低学习效率,这样比起来,我们计算机专业的从业者有明显的学习优势。

编码的2个基本原则

之前一篇关于信息论的文章《序列化的极限》里好像提过一次相关原则:

IEEE浮点数的设计缺陷

今天把这2个原则重新整理一下,原则一叫做“无歧义”,原则二叫做“无冗余”。

信息论要求编码值(序列化的二进制值)与实际含义一一对应,才能将信息压缩至最小,而打破一一对应关系的情况分为2种:

  • 歧义:同一种编码有多个不同的含义

  • 冗余:多种编码对应同一个含义

用一句话概括,编码值(0和1的bit流)和实际含义要一一对应,不多不少,才能达到最优编码。

令人尴尬的IEEE浮点数

最近帮公司开发了一套序列化格式,花了很多时间在“如何存储小数”这个问题上,好像当年比尔盖茨和乔布斯也在这个问题上纠结过很久。为什么存储小数这么难呢?因为小数和整数不同在于:整数关心的是数值的大小,小数关心的是“精度”,整数的编码体积和数值大小成比例,但小数的体积只和精度高低成比例。体积、大小、进度的下限都是0,上限无穷。

IEEE浮点数是如何存储小数的呢?

计算机的发展历史上,用二进制存储自然数本是最“自然”的选择,后来为了存储负数,就出现了原码、2补码、zigzag等编码,再后来为了存储浮点数,就出现了3个主流的IEEE标准:

  • 半精度half:16bit

  • 单精度single:32bit

  • 双精度double:64bit

  • ......

其实还有四精度、八精度等丧心病狂无止境的精度类型,以最简单的半精度(binary16)为例:

IEEE浮点数的设计缺陷

这里面有符号位(sign),指数位(exponent),有效位(fraction),解码公式很有趣:


(−1)sign × 2exponent−15 × 1.fraction2


我们来研究一下这个公式。

知道为什么后面有效位(significantbits)前面是“1.”开头而不是“0.”开头嘛?IEEE浮点数缺省补“1”是为了满足之前的原则“无冗余”:二进制小数部分至少有一个“1”,不可能全是0,否则就是整数了。既然这个第1个“1”是确定存在的,那我们编码的时候就可以省掉一个“1”,让解码器给我们加上就行了。这是一种节省空间,或者“偏移”的技巧:IEEE半精度浮点数显性存储10位有效位,但这10位是“面值”,它还要加上一个隐性的“1”才得到实际值。

精度占比较高的小数更常见,地位更高

IEEE浮点数还有一个明智的做法,在公式中,为什么“1.”要放在fraction之前而不是放在之后呢?如果放在之后就是fraction.1,然后指数位就不用-15了。但显然并没有这么做。科学计数法的习惯并不是解释IEEE浮点数放弃这种简单编码方式的理由,它背后真实的原因是千百年来人类对小数的使用习惯:精度占比较高的小数总是更常见。

举个例子,走直觉的话,12345.6和1.23456这2个小数哪个更“好”?我拍个脑袋,感觉后面那个更好,因为12345.6中整数部分远远大于小数部分,这就让我们开始质疑存储这个0.6的意义何在,直接近似存12346这样一个整数不就行了嘛?但1.23456中,精度部分的占比远大于整数部分,从统计意义上,存储1.23456更有意义,存储12345.6“意义不大”。

可以把这个结论作为一个公理,由此我们在实数范畴出现了4个“更常见”:

  • 整数                      >     非整数

  • 绝对值小的数        >     绝对值大的数

  • 正数                      >     负数

  • 精度占比高的数    >     精度占比低的小数

注:大于号比较的是“常见度”。

可是我最后还是放弃了用IEEE浮点数来编码我的小数,因为它有一个致命的缺点:不纯粹。不知出于什么目的,IEEE浮点数保留了NaN和±infinity这两个在现代编程语言中几乎毫无意义的常量,而NaN和编码不是一对一的,也就是说有一堆不同的binary16都表示NaN,这打破了信息论“无冗余”原则,打破这一原则还有它的±0。

Exponent Significand = zero Significand ≠ zero Equation
000002 zero, −0 subnormal numbers (−1)signbit × 2−14 × 0.significantbits2
000012, ..., 111102 normalized value (−1)signbit × 2exponent−15 × 1.significantbits2
111112 ±infinity NaN (quiet, signalling)

这张表格是Wikipedia上的,主要揭露了半精度浮点数的特殊情况:强行“腾出”的NaN、±infinity、-0。

无奈,只得重新设计小数编码,需要明确的是,浮点数只是小数的编码之一,而IEEE浮点数又是常规浮点数的一种变体,因为它还兼容整数。我希望设计一种编码纯小数的无冗余完美编码,目前可以想到的做法有三种:

  • 浮点数编码:存储【指数,有效部位】

  • 分数编码:存储【分子,分母】

  • 小数点分隔式:存储【整数部分,小数部分】

分数编码的好处在于能够精确地编码任意进制的小数,比如十进制的0.1就能存储为【1, 10】。但分数编码也造成了冗余,因为分子和分母各乘以一个数,分数值不变,所以分数编码被淘汰掉了。

经过漫长的思考,我终于想出了一套基于小数点分隔式的小数编码,暂时命名为“精度反转算法”,名字一听就很有噱头,下一章将具体分析精度反转算法的理论依据。

自上次吐槽Utf8以后又把IEEE浮点数给骂了一遍,真爽。


腾飞大厦