论文地址: Number Parsing at a Gigabyte per Second
符号约定
| 符号 | 说明 |
|---|---|
| \(m\) | 二进制有效数字(非负整数, 通常在\([2^{52}, 2^{53})\))间 |
| \(p\) | 二进制指数(可正可负的整数) |
| \(m \times 2^{p}\) | 非负浮点数的一般形式 |
| \(w\) | 十进制有效数字(非负整数, 通常在\([0, 2^{64})\))间 |
| \(q\) | 十进制指数(可正可负的整数) |
| \(w \times 10^{q}\) | 十进制非负小数的一般形式 |
| \([x]\) | 最接近\(x\)的整数, 四舍六入五成双 |
| \(\lfloor x\rfloor\) | \(x\)下取整 |
| \(\lceil x \rceil\) | \(x\)上取整 |
| 后缀0 | 当\(x\)可被\(2^{k}\)整除时, 称\(x\)有\(k\in \mathbb{N}\)个后缀0 |
字符串解析
算法流程如下:
- 使用一些字符串上的把戏, 迅速的把有效数字和指数提取出来
- 处理极大值和极小值, 分别置零和无穷.
- 归一化\(w\), 使得\(w\in [2^{63}, 2^{64})\)
- 为了将\(w\)转换成\(m\), 我们可以进行近似: \(w \times 10^{q}=w \times 5^{q} \times 2^{q} \approx m \times 2^{p}\). 使用128bit值\(T_{q}\)近似表示\(5^{q}\)(负指数也是如此), 从而可以使用128bit值\(z=w \times T_{q}\)近似表示\(w \times 5^{q}\)
- 检查是否需要退化到更高精度的方法, 即无法证明\(z\)对\(w \times 5^{q}\)足够近似(实际上只有\(q\notin [-27, 55]\)时才会发生)
- 从\(z\)中计算期望的二进制有效数字, 并增加一位用于舍入
- 计算二进制指数
- 处理数值过大或过小以及舍入问题