引擎技术漫游指南:有理数与编码


3楼猫 发布时间:2023-10-21 04:32:22 作者:TirelessKoriel Language

我们先从一个简单的问题入手。

1. 什么是科学计数法?

假设,我们现在要记录一个数字:317464826129。这是我们老板的私人户头上存款金额。
这个金额比较大,足足有十二位数,大约在三千亿左右。
为了防止我们忘记这个数字,我们打算把它记录下来,但是我们手头只有一张很小很小的纸片,大约只能记录六个字符。这个时候我们该怎么做呢?
幸好我们中间有个聪明人,他提议我们可以使用科学计数法,记下 317e11 这串字符。按照科学计数法的规则,其中 e 就代表 10 的次方,e 后面的数字表示幂数,首位数字后面要加一个小数点。那么这串字符等同于 3.17 x 10^11 。
这样我们就用有限的空间存储了一个超级大的数字。不仅如此,如果还有差不多数量级的金额加进来,我们要计算的数字也比原来的数字小得多。我们虽然丢失了精度,但是三千一百七十亿三千一百七十零几亿对于老板来说区别不大。
就这样我们完成了一次对超大金额的记录,这可是好大一笔钱。
从上面这个例子我们可以看出,科学计数法虽然在一定程度上(取决于有效数字位数)丢失了精度,但是换来的是更小巧的存储空间和更便捷的计算过程。而且科学计数法不仅对很大的数字有效,对于那些很小的数字(绝对值无限接近于零),同样有效。例如:317e-11 = 0.00000000000317。这是一个很小的数字,科学计数法一样以便捷的方式记录了它。
那么,说了这么多,科学计数法与有理数的编码又有什么关系呢?
让我们来做一个小小的尝试。

2. 创造一套有理数的编码规则吧

首先,我们就以常见的 32 位二进制数来存储我们的有理数。之后以我们朴素的想法,我们可能会直接想到就将有理数分为整数和小数部分,然后分别用二进制表示它们,再将它们组合到一起。
我们可以用一个具体的例子来尝试一下,比如 32.16 这个数字,按照上面我们定下的规则,表示为二进制就是 100000.10000。这只是比较直观的形式,计算机实际存储这个数字的时候,要将 32 位二进制全部补满。32位二进制中我们要预留一位用来表示正负,剩下的31位分为两半,整数部分各占15位,小数部分占16位,那么 32.16 这个数字在计算机中实际的存储形式应该是:
100000000010000000000000000010000
这种做法非常简单,而且看起来好像还不错。
那我们可以试着计算一下在这种方式下,有理数在精度方面表现如何。
整数部分是 15 位二进制,精度即为 2^15 = 32768
小数部分是 16 位二进制,精度即为 2^16 = 65536
这么一看这种有理数的编码方式在精度方面的问题很大:它的整数部分能表示的最大值太小,小数部分能表示的最小值又太大。
而且由于整数部分与小数部分所包含的二进制位数是固定的,所以在实际使用中,有很大可能导致数位的浪费,例如我们想用这个规则存储圆周率,3.1415926,这时我们的规则将导致小数部分不够用(1415926 > 65536),而整数部分只用到了两位(3 二进制即为 11)。小数部分不够用,而整数部分却还有余,这种情况下我们可以说整数位有 12 位被“浪费”了。
我们还可以从其他角度来进一步理解这种所谓“浪费”。例如,在航天工程中,地月距离 384403 千米,从行星与卫星的角度来看,这种数值已经可以算是精确的了,我们不会在意这个数字后面的小数部分。但是在航天相关的计算机程序中,从计算或各种算法的角度出发来考虑,你不能保证这个数值的存储就一定能用整形(int)。如果用有理数存储,那么上面提到过的“浪费”就又发生了。
这种例子在各种工程中不胜枚举。
那么,从上面这次失败的尝试中,我们或许能得到一条关于有理数编码规则的重要启迪:在对有理数进行编码时,如果整数与小数部分所占的位数可以动态的浮动就好了 。
也就是说,当我们的有理数足够小(绝对值接近零),那么小数部分所占位数就会增加,这样就能保证小数部分的精度;当我们的有理数足够大(绝对值远离零),我那么整数部分的所占位数就会增加,这样就能保证整数部分的精度。这种“浮动”能给我们的编码规则更强的适应性。
对,浮动,整数与小数占位比例能浮动的数。

3. 那我们就叫它浮点数吧

我们以数字 19.625 为例,我们先来处理整数部分。
我们要将整数部分 19 转换位二进制数,用“除二取余”法来计算,即,首先将目标整数除以二,得到的商作为新的目标数继续除以二,重复上述过程,直到商为零。将此过程得到的所有余数,依次从右到左(从低位到高位)排列,就得到了该整数的二进制表示形式,我们来演示一下计算过程:
19 ÷ 2 = 9 余 1;
9 ÷ 2 = 4 余 1;
4 ÷ 2 = 2 余 0;
2 ÷ 2 = 1 余 0;
1 ÷ 2 = 0 余 1;
19 的二进制表示即为:10011
接下来我们以类似的方法,来将小数部分的数值转化为二进制,小数部分的处理叫做“乘二取整”法,即将目标小数乘以二,再取结果小数部分继续乘以二,重复以上过程,直到小数部分消失。将此过程中产生的整数部分(非 1 即 0)依次从右到左(从低位到高位)排列,就得到了该小数的二进制形式:
0.625 x 2 = 1.25 ,整数部分为 1;
0.25 x 2 = 0.5 ,整数部分为 0;
0.5 x 2 = 1 ,整数部分为 1;
0.625 的二进制表示即为:0.101
我们可以观察到,小数部分转为二进制时,与整数部分的方法是对称的,镜像的。一个是除二取余,一个是乘二取整。我们可以通过一个数轴,来进一步的感受这种对称:
图中最上方绿色数值组成了一个简单的横向数轴,最大值为 4,最小值为 -4 。
观察数轴下方白色数字可以看出,数轴的值表示 2 的幂数,数轴下方蓝色数字表示相应的幂数下的值。我们可以通过这个数轴来快速对整数部分进行二进制转换:
因为,16 + 2 + 1 = 19,所以 16,2,1位置处的二进制为 1,即 19 的二进制表示为 10011。
同样的,这个数轴还可以用相同的方法来快速转换小数部分的值:
因为 0.625 = 0.5 + 0.125,所以 0.5 ,0.125 位置处的二进制为1,即 0.625 的二进制表示为 0.101
这两个结果与前面我们计算得到的值是一致的,同时我们还能从数轴上看到两种方法的对称性。
这种方法与我们自己创造的有理数编码非常不同,虽然看起来和处理整数部分的方法如此对称,但是给我们的最直观的感受是这种方式更加复杂,那么我们为什么要这么处理呢?
原因就是这种处理方式与我们前面提到的所谓浮动更加契合。我们可以用一个例子来展示其中的原理。
假设我们现在有一个很大的数字,它的整数部分为 134217728。为了能保证整数部分的数字保存完整,我们给整数部分分配了 28 位二进制。那么也就是说,我们只有 4 位二进制可以用来表示小数了。
4 位二进制用来表示小数的精度又如何呢?我们来计算一下。
0.0001 = 0.0625
0.0001 + 0.0001 = 0.0010 = 0.125
0.0010 + 0.0001 = 0.0011 = 0.1875
……
观察上述计算过程我们能够发现,按照这种编码规则,只有 4 位二进制的小数能表达的值都是 0.0625 的倍数,也就是说,这个小数的值不仅不是连续的,能表示的连续的两个数字之间的间隔甚至非常大!我们甚至无法表示 0.0626。这种精度看起来是无法接受的。
但是,我们的整数部分整整有 134217728 这么大,从工程的角度来说,这个时候我们还会在意小数部分的大小吗?可以说这种精度的浮动,正是我们想要的结果!
让我们再进一步,我们将小数部分的位数增加到 5,再来看一下精度:
0.00001 = 0.03125
0.00001 + 0.00001 = 0.00010 = 0.0625
0.00010 + 0.00001 = 0.00011 = 0.09375
……
观察可以发现,当我们提升了小数部分所占位数,这种编码方式下的小数精度也提升了。所占位数为 4 时,小数间的间隔为 0.0625,所占位数为 5 时,小数间的间隔为 0.03125,提升了一倍。我们不难推测,随着小数部分所占位数提升,小数间的间隔也会更小,更小的小数间隔代表着更加连续(虽然还是离散的)小数排列,同时也代表着精度的提高。
上面的计算过程说明了浮动机制在这种编码规则下,是如何保证精度平衡的(整数与小数部分)。
那么接下来我们要面临的问就是,我们该如何浮动呢?
我们最开始讨论过的科学计数法,就是用来解决这个问题的。
还是以上面提到过的数字 19.625 为例,我们上面计算得到的整数部分与小数部分结合起来即为:10011.101
我们尝试用十进制的科学计数法来类比二进制的科学计数法,我们能得到 10011.101 科学计数表达形式:1.0011101 x 2^4,注意!这个地方很重要,2 的 4 次幂表示我们将小数点向左移动了 4 位(与十进制的科学计数法规则一致,只不过这里是二进制,所以是 2 的指数),此时我们原本数字的正数部分与小数部分共同组成了科学计数法表达后的小数部分!
想要保存这个形式的数字,我们只需要三个关键值:一是数字的正负号,简称符号;二是记录这个形式下的小数部分,即 0011101,我们可以把它称为尾数;三是 2 的幂数,即 4,它代表了我们的小数点移动了几位,所以我们可以把它称为偏移指数。有了这三个关键值我们就能回溯出原始的二进制值。
那么为了保存这三个关键值,我们可以将 32 位二进制,做以下这种分隔:
结合上图所示与我们的例子,我们可知:
首位是符号位,19.625 位正数,所以此位为1;
后 8 位是偏移指数位,1.0011101 x 2^4 中 2 的指数为 4,即小数点偏移了 4 位,所以此位补满 8 位后为:00000100;
后 23 位是尾数位,1.0011101 x 2^4 中尾数为 0011101,所以此位补满 23 位后为:00111010000000000000000。
正如我们上面提到过的,科学计数法导致我们的小数点发生了偏移,就本例来说,我们的小数点向左偏移了 4 位,也就是说我们的整数部分与小数部分共同组成了尾数,尾数位部分的位数有限,所以整数部分与小数部分在组合的同时,也完成了对尾数位的分配。整数部分越大,它在尾数位中所占位数就越高,小数部分所占位数就越小。
这还没完,在我们为 10011.101 做科学计数法表达时,小数点是向左移动的,这是因为我们的目标值 19.125 是一个带有整数位的数字,如果我们是一个比较小的小数呢?
例如,我们现在有一个数字 0.15625,二进制转换后为 0.00101,科学计数法表达为 1.01 x 2^-3。该科学计数的尾数为01,这很简单;问题是指数为 -3 ,我们该如何在指数位中表达负数呢?
我们只需要模仿现有的符号位,将偏移指数位的首位作为指数位的符号位即可。当偏移指数位的首位变为偏移指数的符号位时,我们原本的 8 位二进制就缩减为 7 位,最大值为 1111111 = 127。那么如果偏移指数为正数时,我们就将偏移指数加上 127 ,得到的结果转为二进制时,便自然会变成8 位,并且首位为 1 ,这就自动完成了首位表示符号位的操作。
我们展示一下过程。
十进制:127 + 1 = 128
二进制:01111111 + 0000001 = 10000000
这就免除了其他附加操作,只需要以 127 为基础做加法,就能自动完成符号位的匹配。
所以 0.15625,科学计数位 1.01 x 2^-3,用我们的编码方式编码后,在计算机中的二进制表示就是:
1 01111100 01000000000000000000000
其中偏移指数为的计算为,127 + (-3)= 124 = 01111100,可见偏移指数为首位为 0,与偏移指数值 -3 符号匹配。
同理,因为我们重新定义了指数位,所以我们也要修改 19.125 在计算机中的二进制表示:
1 10000011 10010010000000000000000
其中偏移指数为的计算为,127 + 4 = 131 = 10000011,可见偏移指数为首位为 1,与偏移指数值 4 符号匹配。
其实通过对偏移指数位的理解,我们还会发现一个问题。偏移指数位共有 8 位,抛开符号位还剩 7 位,也就是说,小数点向整数偏移时,最多能偏移 127 位,加上整数位的1(例如1.01 x 2^-3,整数位必然为1),也就是说,这种编码方式能保存的值最大为 2^128 = 3.4*10^38,但是我们实际存储数值的二进制位数只有 23 位,这好像并不合理。
这个问题的答案其实还是我们之前讨论过的极大值不在乎极小值的道理。3.4*10^38 尺度的值,不会在意小数,甚至不会在意上亿的值,上千亿的值上万亿的值它都不在乎,这些值对于它来说,都太小了。当数值巨大时,科学计数法会驱动小数点疯狂的向整数方向移动,那些被小数点抛弃,并且无法被 23 位二进制容纳的数值都会被抛弃。也就是说,这种情况下,不仅小数会被无视,连那些不够大的整数部分也会被忽略。这么看来,对于极大的整数来说,我们的编码规则会舍弃精度来换取对极大值的包容。
对于小数来说正好相反。我们的编码机制会使得越小的值精度越高。这个机制我们在上面关于数轴的讨论中就提到过,总结来说就是在这个编码规则下,极小数的精度就是极小数本身。
这正是我们想要达到的效果:值越大,精度越低,因为大值不在乎小值;值越小,精度越高,因为越小的值越在乎自己能有多小。
以上所述,就是 IEEE754 标准,它被广泛适用于浮点数的编码操作。
最后我们可以再来做两个试验,来验证我们对规则的描述是否正确。
我们可以查询到,通常 32 位浮点数的精度为:±1.18*10^-38 ~ ±3.4*10^38。
其中 ±3.4*10^38 符合我们对偏移指数做进一步解释时所提到的最大整数值。
接着我们验证一下最小绝对值 1.18*10^-38。
由偏移指数位的编码规则可知,当小数点向小数偏移时,最多能偏移 126 位,即这种情况下最小值为:2^-126 =
验证成功。

© 2022 3楼猫 下载APP 站点地图 广告合作:asmrly666@gmail.com