浮点数

2.4 浮点数

浮点数表示是对可以用$V=x*2^y$表示的有理数的编码。当计算非常大的数字(|V|>=0)或者与0非常接近的数字时是非常有用。更普遍的说，是对实际算术的近似。

直到1980年代，计算机制造商还是在设计自己的浮点数表示方法和计算方法。另外他们不是特别担心计算的精准程度。把计算速度和实现的简单程度看的比精准度更加重要。

随着1985年IEEE标准754(一个精雕细琢的关于怎么表示浮点数和怎么操作浮点数的标准)的出现，这一切被改变了。这项工作始于1976年，在英特尔的赞助下设计了8087，一个为8086处理器提供浮点数支持的芯片。因特尔雇佣了加利福尼亚伯克利分校的教授威廉卡亨作为顾问，帮助他们设计未来处理器的浮点数标准。他们允许卡亨与在一个委员会合作，在IEEE的支持下，制作一个全行业通用的标准。这个委员会最终接受了一个非常接近卡亨为因特尔设计的版本。今天，几乎所有的计算机都支持IEEE浮点标准。这个已经极大的提高了跨平台的科学计算应用程序的兼容性。

这一章我们会看到浮点数怎么用IEEE规定的格式表示的。并且探索rounding的问题，就是当一个数字不能准确的表示的时候，必须上调或者下调。然后探讨加和乘法的问题。很多程序员认为浮点数是无趣的。做最坏的情况下还可能是神秘的，不可理解的。我们将会看到基于非常少量的规则和一致性的IEEE标准，是非常优雅和容易理解的。

2.4.1 分数二进制

了解浮点数，第一步是了解怎么用二级制表示分数。二进制分数采用以下方式

d_md_{m-1}d_{m-2}……d_{0}.d_{-1}d_{-2}……d_{-n}

其中小数点左边的数字位置k，对分数的值的贡献是 $2^k$,小数点右边的位置k，对分数的贡献是$2^{-k}$
对于以下小数

b_mb_{m-1}···b_1b_0.b_{-1}b_{-2}···b_{-n+1}b_{-n}

它的十进制值是

b=\sum_{i=-n}^m2^i*b_i

2.4.2 IEEE标准的浮点表示方式

如前面章节讨论，按为表示发法，在表示非常大的数字是非常有效。例如表示$5 * 2^{100}$如果用普通的二进制表示方法，需要103位，101后面加上100个0。但是如果用$x*2^y$的这种表示方式，将会非常节省空间。

IEEE浮点标准表示可以用$V=(-1)^s * M * 2^E$表示的数字。

• 符号s表示是正数还是负数。s=1表示负数，s=0表示正数
• 尾数M 表示的是一个 1<M<2或者0<M<1的数字
• $2^E$是用来对M做权重修改的。

对于一个32位浮点数，分为三个区域

• 最高位s表示符号
• 中间的k位是指数域，exp=e_{k-1}e_{k-2}···e_0表示指数E
• 后面的n位，是分数区域。$frac=f_{n-1}f_{n-1}····f_0$表示尾数M。但是Mde值的计算方式，依赖于指数的值是否等于0。

下图表示了两个常用的浮点数的分区方法[图片上传失败...(image-8bdbaa-1609863011572)]

• 在C中，32位的单精度浮点数，用1位表示s，8位表示指数域，剩下23位表示尾数。记做k=8, n=23.
• 在C中，64位的双精度浮点数，用1位表示s，11位表示指数域，剩下的52位表示尾数。记做k=11, n=52.

根据指数区域的值的不同，浮点数的值分成三种表示方式。

1. 标准化的值

这个是大部分情况。当指数域不全是0并且也不全是1时，这个浮点数一个标准化的浮点数。此时的计算方式如下:

1. 指数的E的计算方式
   $E=e-Bias$其中$Bias=2^{k-1}-1$, $e=e_{k-1}e_{k-2}···e_1e_0$.
   e是一个无符号整数，取值k为无符号整型的范围为0~$2^k-1$,但是此处不能全为1，也不全为0所以

1<=e<=2^{k} - 2

所以E的取值范围为

1-Bias<=E<=2^{k} -2 -Bias

也就是

-2^{k-1} + 2 <= E <= 2^{k-1} -1

对于32为单精度浮点数来说k=8，所以标准化表示32位浮点数的指数E的取值范围是$-126<=E<=127$.对于k=11的64位双精度浮点数来说就是$-1022<=E<=1023$

2. 尾数M的计算
   分数区域被当做小数后面的部分来计算的。$f_1f_2···f_{n-1}f_{n}$是被当做$0.f_1f_2···f_{n-1}f_{n}$的值来计算的。实质上，标准话浮点数的表示中，小数左边的部分默认为是1的所以小数部分的值的计算是$1.f_1f_2···f_{n-1}f_{n}$ 所以尾数部分M的值是1<=M<2

2. 非标准化浮点数

当指数区域部分全部是0是，这个浮点数叫做一个非标准化浮点数。

1. 非标准化浮点数的指数E=1-Bias，也就是$E=-2^{k-1}$.
2. 尾数部分M=f。
   非标准化浮点数有两个目的

• 非标准化浮点数可以表示0，虽然有+0.0和-0.0
• 可以看到$E=-2^{k-1}$.所以可以用来表示非常小的数。接近于0

3 特殊浮点数值

当指数区域都是1时，这个是一个特殊浮点数值。

• 当分数区域全部是1是，表示无限大。当s=0时，表示$+\infty$,当s=1时，表示$-\infty$
• 当分数区域不全部是1时，这个浮点数叫做NaN，'not a number'的缩写。当有一些值不能用实数表示的时候，比方说$\sqrt{-1}$

2.4.3 分数的例子[图片上传失败...(image-892dd0-1609863011572)]

上图中是表示一个k=4，n=3 s=0的浮点数的所有可能形态。

• 上图中从非标准化的浮点数开始，当s=0时，$E=1-Bias=1-2^{k-1}+1$=-6.
  所以最小的尾数$M=f=1*2^{-n}$,所以非标准化浮点数能表示最小正数是$V=M*2^E=2^{-3}*2^{-6}=\frac1{512}$最大正数就是当$M_{max}=\frac78$,此时$Vmax=\frac78*2^{-6}=\frac7{512}$
• 增大指数，就变成标准化浮点数E的取值范围是$-2^{k-1}+2<=E<=2^{k-1}-1$.尾数M的最大取值是$M=1.f_1f_2f_3=\frac{15}8$.所以规范化浮点数表示的最大数是$\frac{15}8*2^7=240$超过这个数字就溢出了，就是$+\infty$

Tips:
有个有意思的点就是，上图中，左边的二级制表示方法是升序的，右边的十进制数值也是升序的。IEEE这样设计，是为了浮点数能够用整型的方法进行排序。但是当s=1，是负数时，就不是这样的。这个问题可以用不让浮点数排序的方式来解决。

2.4.4 Rounding

浮点算法由于精度和范围的限制，只能接近实数算法。比方说对于数值x，
我们需要一个系统性的方法找到最接近能够用浮点数表示的的$x^*$，这个就是rounding operation主要要做的事情。关键是确定在两个可能数值见确定一个数值的方向。比方说要用浮点表示最解决的1.5,那最接近的是1还是2呢。另外一个方法是一个区间记做$x^-$和$x^+$, $x^-<=x^*<=x^+$.浮点数的rounding定义了四种rounding模式。默认的模式找到一个最接近的值，另外三种是找到最大和最下区间。

Round-to-even尝试找到最解决的匹配。
唯一的设计决策是确定rounding后的值在两个可能结果之间的影响。Round-to-even可以是向上舍入或者向下舍入，主要看最后以为舍入的值是不是偶数。所以它把1.5和2.5都rounding成了2。 这么设计的原因主要是当数据很多时，rounding后的数据总量或者平均值不会比原先的总量或者平均值大很多或者小很多。取偶数能保证差不多持平。

例如我们rounding 1.234999 成1.23 ，把1.2350001 rounding成1.24，这个是没有争议的。因为这两个数字都不在1.23和1.24之间，但是我们把1.235rouding成1.24因为4是偶数。

同样这个方法可以用于对二级制分数上。我们认为0是偶数，1是奇数。
所以在rounding的时候，在这个数字处于中间值的时候，我们考虑的是最后的数字的最后偏向于0还是1。例如同样是对小数点后第三位进行rounding，是舍去，还是进位呢

• $10.000011_2$($2\frac3{32}$)舍去的话是$10.00_2$(2)，进一位的话是$10.01(2\frac1{4})$. 很明显距离2更近。所以选择$10.00_2$(2)
• $10.00110_2(2\frac3{16})$ 在$10.00(2)$和$10.01(2\frac14)$之间距离$10.01(2\frac14)$更近。
• $10.11100_2(2\frac78)$距离$11.00(3)$和$10.11(2\frac68)$的距离是一样的，这个时候按照最后以为是偶数的原则选择$11.00(3)$
• $10.10100(2\frac58)$距离$10.11(2\frac68)$和$10.10(2\frac48)$的距离是一样的，我们选择根据最后以为偶数原则选择$10.10(2\frac48)$

2.4.5浮点数操作

2.4.5.1 加法

IEEE标准给浮点数加法和乘法制定了一个简单的规则。把$V=x*2^y$这样表示数值中x和y的计算当做实数的计算，然后加上round的操作。

实践上，设计者添加了一些聪明的设计技巧来避免一些需要充足的精确度来保证准确的round结果。当其中的一个参数是一个特定值的时候，比方说$-0, \infty$ 或者NaN。IEEE标准惯例尝试做一些可以被理解的的尝试。比方说$1/-0$返回$-\infty$,$1/+0$被定义为$+\infty$

IEEE标准的一个强大之处在于独立于软件和硬件。我们只需要考虑算法上的结构就好了，不用考虑具体怎么被实现。

前面我们讲过整型的加法，无符号的有符号的。他们都是可替换的，即a + b + c = b + c + a.但是对于浮点数来说，因为从在rounding的操作，所以可替换原则不成立。 但是 两个浮点数 x + y = y + x. 但是浮点数 (a + b) + c != a + (b + c). 例如 (3.14 + 1e10) - 1e10 = 0. 3.14在rounding的过程中丢失了。 但是3.14 + (1e10 - 1e10) = 3.14.

对于绝大多数浮点数x来说 x + (-x) = 0,但是也有例外
$+\infty + -\infty=NaN$.
对于所有的x来说：
NaN + x = NaN

浮点数不符合结合律这个特性，是区别于整型计算的最大特性。这样会导致编译器在编译时候，不敢去做优化。

另外一方面，浮点数加法符合以下特性
对于任何非NaN的a, b,x 如果a >= b, 那么x + a >= x + b.

2.4.5.2 浮点数乘法

浮点数和加法一样同样是可以互换的，同样由于rounding的操作，是不符合结合律。例如：
1e20(1e20-1e20) = 0.0
1e201e20-1e20*1e20=NaN

同样，乘法符合单调性,对于任何非NaN的a,b,c来说：
a>=b并且c>=0 ==> ac>=bc
a>=b并且c<=0 ===> ac<=bc.

同样的对于任意非NaN的a：
a*a>=0.
无符号和有符号整型都不符合单一性。

2.4.6 C中的浮点数

所有版本的C语言都提供两种类型的浮点数，单精度浮点数和双精度浮点数。
C语言标准不要求机器使用IEEE标准浮点数。所有没有标准的方法来改变rounding的方法以及获取特殊的值$-0, +\infty -\infty$或者NaN。大部分系统通过头文件和程序库的结合来提供这些特性。但是细节因不同机器实现而不同。

转换

• 32位int到float。 不会溢出，但是会rounded
• 32位int到double float。可以准备表示。因为64的double有足够的位。
• double to float。 可能正溢出或者负溢出。因为范围被缩小了。有可能被rounded
• 从float，double 转化为int。小数部分可能会被丢弃。如1.99会变成1， -1.99可能变成-1。另外值可能会溢出。C标准没有对这个点进行特别定义。