计算机系统中的代数结构(浮点型)

在上一篇文章中,已经解释了整型(无符号与补码)中的代数结构,并证明了两者是同构的。这一篇文章将介绍浮点型中的代数结构。

不过,对于其中提到的基本概念(如:阿贝尔群、环)将不再介绍。

浮点数的性质

我们知道,与整型不同,浮点数系统中存在三种数。

  • 规格化的数
  • 非规格化的数
  • 特殊值(INF、NaN)

其中 INF 和 NaN 都是不满足数的运算性质的。如 \[ INF + 1 = INF \] 并且由于舍入误差的存在,浮点数运算的结果和真实世界中的结果并不一致。比如

\[ 0.2 + 0.1 = 0.30000000000000004 \]

这是因为,同样是有限的状态空间,整型保存的都是一个数的精确值,而浮点数保存的都是近似值。(整数都是可列的,而实数是稠密的)。就算是定点小数,也是数轴上离散的点。

出于上述原因,浮点数及其上运算其实并非一个封闭的代数系统。(主要是因为INF和NaN的存在)。这里我们将使其与阿贝尔群和交换环比较。(从上一篇博客我们已经知道了这两种代数结构的具体含义,并且了解了现实世界中实数运算就满足这样的性质)。但需要注意的是,浮点数及其上运算并非严格意义上的这两种代数结构。

浮点型与阿贝尔群

回忆上一篇文章中对阿贝尔群的描述:

  • 封闭性:\(0 \leq u +_{f} v \leq 2^w -1\)
  • 交换律:\(u +_{f} v = v +_{f} + u\)
  • 结合律:\(t +_{f} (u +_{f} v) = (t +_{f} u) +_{f} v\)
  • 零元:\(u +_{f} 0 = u\)
  • 逆元:\(u^{-1}=2^w-u\)

我们自然期望浮点数满足这样的性质。但是因为NaN和INF的存在,浮点数及其上运算并不能严格满足。

封闭性

\[ arcsin(5\pi) = NaN \]\[ 0.0 \ 0.0 = INF \]

NaN和INF并非数,这里已经不满足封闭性了。

交换律与结合律

\[ 3.14 + 10000000000 - 10000000000 = 0 \]\[ 3.14 + (10000000000 - 10000000000) = 3.14 \] 这里可以看出,机器运算的结果和真实世界中的正确结果并不相同。主要原因是运算中的舍入误差。同时,因为上溢的存在也不能满足交换律与结合律。

逆元和零元

对于零元 \[ INF + 0 = INF \]\[ NaN + 0 = NaN \] 阿贝尔群的零元性质还存在。 但对于逆元性质就不存在了。 \[ INF - INF = NaN \]\[ NaN - NaN = NaN \]

浮点型与交换环

从上一个部分的分析,我们其实也已经能看出,浮点型及其上运算并不是一个严格的交换环。 主要原因就在于INF、NaN的存在,和舍入误差的存在。

总结

这篇文章中只介绍了浮点数及其运算的性质,然后同严格的阿贝尔群和交换环进行了比较。之所以不介绍其后具体的原因,是因为想站在一个更抽象的角度去描述计算机的代数结构。但了解其后的原因却是有必要的。 比如INF、NaN为什么没有逆元。以及文中没有提到的,却也影响浮点数及其运算称为标准的阿贝尔群和交换环的元素: \(+0,-0\) 。(想想数学里的左右极限?) 背后具体设计思路在本文中不再赘述,但的确是非常重要且精妙的。

回到为什么要用代数结构的思想去描述计算机系统中的数及其运算。一方面,代数结构给了我们相关的工具,去严格描述。计算机世界要求的本来就是逻辑严密。另一方面,了解代数结构的相关知识,还可以加深对布尔代数等计算机系统中的其他代数系统的学习大有脾益。

更为引申的意义:函数式编程对代数结构要求颇多。作为一种与传统命令时编程完全不同的思想,函数式编程随着云计算的发展开始从学术走向工程,一个渴望称为优秀工程师的人不可以不了解这个领域。但同时,函数式编程对数学要求极高,诸如抽象代数、范畴论、泛函分析等(我一门都没学过...)。这两篇文章借助浮点数与整型的具体例子,介绍了代数结构的基本知识。其中多次提到的幺半群,在语言haskell中就对应有monad。

这两篇博文是我在自学了极少的代数结构知识下写出来的,其中肯定会有各种纰漏。希望你看出来了可以指出。之所以不介绍布尔代数的结构,实在是因为自己还没有看到那里去....

两篇文章,就当作是写给自己的科普好了~

DeeCamp 2019 计算机系统中的代数结构(整型)

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×