Fundamentals

evaluating a polynomial use nested multiplication (Horner's method)

$$c_1 + c_2x + c_3x^2 + c_4x^3 + c_5x^4 \\ = c_1 + x(c_2 + x(c_3 + x(c_4 + x(c_5))))$$

总共4次乘法，4次加法

Example

$$\begin{align} P(x) &= 4x^5 + 7x^8 - 3x^{11} + 2x^{14} \\ &x^5(4+x^3(7+x^3(-3+x^3\cdot 2))) \end{align}$$

binary numbers

Decimal to binary

整数十进制转二进制，不断除2(到0停止)，记下余数(0/1)，倒写余数即2进制表示

小数部分十进制转二进制

$$Example 1. 求 0.7的二进制表示 \\\\ 0.7 \times 2 = 0.4 + 1 \\ 0.4 \times 2 = 0.8 + 0 \\ 0.8 \times 2 = 0.6 + 1 \\ 0.6 \times 2 = 0.2 + 1 \\ \cdots \\\\ (0.7)_{10} = (0.1011\cdots)_2 \\\\ Example 2. 求0.5的二进制表示 \\\\ 0.5 \times 2 = 0.0 + 1\\\\ (0.5)_{10} = (0.1)_2$$

Floating Point Representation Of Real Numbers

Floating Point Formats

浮点数的表示由 符号位(sign)、尾数(mantissa)、指数(exponent)三部分构成

分类：单精度(double precision)，双精度(double precision)，extended precision

各部分在不同精度浮点数下占用的bits数量

precision	sign	exponent	mantissa
single	1	8	23
double	1	11	52
long double	1	15	64

正规的 IEEE 浮点数长这样: $\pm 1.bbb\cdots b\times 2^p$

the leading bit must be 1 , 所以 9 在浮点数下的表示为 $+1.001 \times 2^3$

machine epsilon: $\epsilon_{mach}$ 表示1 和 比1大的最小的浮点数之间的差

对于 双精度浮点数来说 , $\epsilon_{mach} = 2^{-52}$

当表示一些非常长的小数(极端一点比如无限小数)，mantissa 只有52位，装不下。所以要做舍入(rounding)

Rounding Rules

对于双精度浮点数，如果第53位(从左往右数)尾数是0，那就直接舍去，后边的直接截断。

如果第53位是1，就向上进位(给第52位 + 1 )

❗️特殊情况
如果第53位是1，后边的全是0，那么只有52位是1的时候才进位

把实数转化成IEEE浮点数的步骤

1.先用二进制表示
2.shift radix point to the right of leftmost 1, and compensate with the exponent
3.执行舍入

Example: 把9.4用双精度浮点数进行表示

$(9.4)_{10} = (1001.\overline{0110}) = 1.001\overline{0110} \times 2^3$

","分割方便阅读，未舍入之前长下边这样

$$+1.0010, 1100, 1100, 1100, 1100, 1100, 1100, 1100, 1100, 1100, 1100, 1100, 1100 \underbrace{,\overline{1100}}_{超过尾数长度的部分} \times 2^3$$

舍入后

$$+1.0010, 1100, 1100, 1100, 1100, 1100, 1100, 1100, 1100, 1100, 1100, 1100, 1101 \times 2^3$$

Rounding Error

用 $fl(x)$ 函数表示对$x$进行舍入后的值

$$\begin{align} fl(9.4) &= 9.4 + (2^{-52} * 2^3) - (.\overline{1100}\times 2^{-53}\times 2^3) \\ &= 9.4 + 2^{-49} - (.\overline{0110}\times 2^{-51}\times 2^3) \\ &= 9.4 + 2^{-49} - 0.4\times 2^{-48} \\ &= 9.4 + (1 - 0.8)\times 2^{-49} \\ &= 9.4 + 0.2\times 2^{-49} \\ \end{align}$$

$0.2\times 2^{-49}$ 称为 rounding error

relative rounding error

$$\frac{|fl(x) - x|}{|x|} \le \frac{1}{2}\epsilon_{mach}$$

Machine representation

bits layout : $se_1e_2\cdots e_{11}b_1b_2\cdots b_{52}$

符号位 0 表示 正 , 1表示负

指数的范围是 -1022到1023,但是二进制表示需要加一个偏移量1023(这里讨论双精度的情况下),加上偏移后的范围是1-2046. 指数部分 0 和 2047预留出来有特殊的用途

1的浮点数表示

$$1.0 = 1.0 \times 2^0 \\\\ ( 0 + 1023 )_{10} = \fbox{011 1111 1111} \\\\ (1.0)_{10} = \fbox{0}\fbox{011 1111 1111}\fbox{ 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 }$$

特殊的指数值2047

2047是用来表示正负无穷的以及NaN的

表示正负无穷的时候尾数为全0,表示NaN的时候尾数随意(但得是非0)

$\infty 的前12bits : \fbox{0111 1111 1111}$
$-\infty 的前12bits : \fbox{1111 1111 1111}$

machine number	example	hex format
$+\infty$	1/0	$7FF0000000000000$
$-\infty$	-1/0	$FFF0000000000000$
$NaN$	0/0	$FFFxxxxxxxxxxxxx$

特殊的指数值 0

当指数是0的时候,不使用标准的浮点数表示方式,而是下面这种

$$\pm 0.b_1b_2\cdots b_52 \times 2^{-1022}$$

$2^{-52}\times 2^{-1022} = 2^{-1074}$ 是双精度浮点数能表示的最小的非零实数
其二进制表示为$\fbox{0}\fbox{000 0000 0000}\fbox{ 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0001 }$

比 $\epsilon_{mach}$小的数是可以被表示的，虽然把这些数加到1上可能会没有任何作用。但是比$2^{-1074}$更小的数字是没法被表示的

术语 underflow 表示运算结果太小了以至于不能被表示

Addition of floating point numbers

浮点数加法先根据对齐指数，然后尾数相加

$$\begin{align} &\hphantom = 1.\fbox{00...0} \times 2^0 + 1.\fbox{00...0}\times 2^{-53} \\ &= 1.\fbox{ 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 } \times 2^0 \\ &+ 0.\fbox{ 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 }1 \times 2^0 \\ \hline &= 1.\fbox{ 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 }1 \times 2^0 \end{align}$$

从结果来看 , $1 + 2^{-53} = 1$
任何比$2^{-53}$更大的数加到1上,都将会大于1