# 快速非舍入缩放：浮点数打印的统一算法框架 > 解析 Russ Cox 的非舍入缩放原语如何统一固定宽度与最短宽度打印，性能超越 Dragonbox、Ryū 等现有算法。 ## 元数据 - 路径: /posts/2026/01/24/fast-unrounded-scaling-floating-point/ - 发布时间: 2026-01-24T06:46:05+08:00 - 分类: [systems](/categories/systems/) - 站点: https://blog.hotdry.top ## 正文 浮点数打印是每个运行时环境都必须解决的底层问题。当你在终端打印一个 `float64`，或通过 `JSON.stringify` 序列化一个数字时，底层都在执行二进制到十进制的转换。这个看似简单的问题在过去五十年间催生了 dozens 种算法，从 1990 年的 Dragon4 到 2018 年的 Ryū、2024 年的 Dragonbox，每一次迭代都在平衡代码复杂度与运行速度。Russ Cox 在 2026 年 1 月发表的研究成果表明，这个问题的解可以比所有人想象的都更简单：他提出的「非舍入缩放」原语不仅统一了打印与解析两种操作，而且实现代码极少，性能却超越了所有已知算法。 ## 问题的本质：二进制的机器与十进制的人眼 浮点数在计算机内部以 `m·2^e` 的形式存储，其中 `m` 是定点整数，`e` 是指数。人类习惯阅读十进制表示，所以 `3.14159` 比它的二进制等价物更容易理解。转换的核心挑战在于：如何在不引入大数运算的前提下，精确计算 `m·2^e·10^p` 的整数部分，同时保留足够的舍入信息。 传统的解决方案大致分为两类。第一类是「足够精度」路线，例如 Grisu3 使用 64 位扩展精度来近似计算边界，如果精度不足则回退到大数运算。这类方法代码复杂，需要精心调优的回退逻辑。第二类是「表驱动」路线，例如 Ryū 和 Dragonbox 预计算 128 位的 10^p 近似值，通过一次乘法完成缩放。这条路线更快，但每种输出模式（固定宽度、最短宽度）需要独立的实现。 Russ Cox 的突破在于找到了第三条路：**非舍入缩放**。这个原语 `uscale(x, e, p) = ⟨x·2^e·10^p⟩` 返回的不是整数，而是一个「非舍入数」，它携带了完整舍入所需的信息，但计算成本几乎等同于一次乘法。 ## 非舍入数：携带舍入信息的紧凑表示 一个实数 `x` 的非舍入形式 `⟨x⟩` 定义为：整数部分 `⌊x⌋` 加上两个额外的位。第一位是「½位」，表示小数部分是否至少为 0.5；第二位是「粘滞位」，表示小数部分是否非零且非 0.5。用公式表达就是 `⟨x⟩ = ⌊4x⌋ | (4x ≠ ⌊4x⌋)`。这两个位恰好对应 IEEE 754 浮点运算中用于舍入的额外精度位。 在 Go 代码中，非舍入数可以用 `uint64` 高效存储： ```go type unrounded uint64 func (u unrounded) floor() uint64 { return uint64((u + 0) >> 2) } func (u unrounded) roundHalfDown() uint64 { return uint64((u + 1) >> 2) } func (u unrounded) round() uint64 { return uint64((u + 1 + (u>>2)&1) >> 2) } func (u unrounded) roundHalfUp() uint64 { return uint64((u + 2) >> 2) } func (u unrounded) ceil() uint64 { return uint64((u + 3) >> 2) } ``` 通过在 `⟨x⟩` 上加 0、1、2、3 再右移两位，可以实现向下舍入、0.5 向下舍入、0.5 向偶数舍入、0.5 向上舍入和向上取整。关键在于：只要粘滞位被置为 1，它就会在所有后续操作中保持为 1，这保证了舍入信息的完整性。 ## 快速非舍入缩放的实现细节 `uscale` 的朴素实现使用大整数运算，这在性能敏感的场景中不可接受。快速实现利用了一个观察：在所有实际使用场景中，`x·2^e·10^p` 的结果始终能放入 64 位整数。这意味着我们可以用定点数近似来替代任意精度运算。 具体策略是为每个 `p` 预计算一个 128 位的 `10^p` 近似值 `pm·2^pe`，其中 `pe = ⌊log2 10^p⌋ - 127`，`pm = ⌈10^p / 2^pe⌉`。这个表覆盖 `p ∈ [-343, 341]`，共 685 个条目，每个条目 16 字节，总共约 11KB。在缩放时，计算 `(x * pm) >> -(e + pe)`，其中移位操作保留了足够的位来设置粘滞位。 优化后的实现更进一步：在很多情况下，只需要计算高 64 位乘法就能确定结果。Russ Cox 的优化代码首先计算 `hi = Mul64(x, pm.hi)`，然后检查 `hi` 的低 `s` 位是否全为零。如果全为零，说明没有位会被移出，直接使用 `hi >> s` 作为结果；否则才计算低 64 位并设置粘滞位。这个优化使得大多数 `uscale` 调用只需要一次宽乘法，而不是两次。 ## 固定宽度打印：17 位足够保证往返精度 固定宽度打印是最常用的场景，例如 `printf("%.17e", f)` 要求输出恰好 17 位有效数字。Russ Cox 的实现先通过近似对数计算确定目标指数 `p`： ```go func FixedWidth(f float64, n int) (d uint64, p int) { if n > 18 { panic("too many digits") } m, e := unpack64(f) p = n - 1 - log10Pow2(e+63) u := uscale(m, prescale(e, p, log2Pow10(p))) d = u.round() if d >= uint64pow10[n] { d, p = u.div(10).round(), p-1 } return d, -p } ``` 这里 `log10Pow2` 使用定点数近似 `(x * 78913) >> 18`，避免了浮点运算的开销。结果 `d` 是整数，`p` 是负指数，最终输出格式为 `d·10^p`。由于 `float64` 的精度保证，最多 17 位就能唯一标识任意值，因此 `n > 18` 会直接 panic。 ## 最短宽度打印：找到最短的往返安全表示 最短宽度打印的目标是使用尽可能少的数字，同时保证解析回来得到原始值。这个问题比固定宽度复杂得多，因为某些「拐点」附近的值存在多个同样短的表示。 Russ Cox 的算法通过计算浮点数邻居的中点来确定有效区间。对于普通情况，邻居间距是 `2^e`，中点间距也是 `2^e`。但对于 2 的幂次方附近的值（指数变化的拐点），下半中点是 `(m - ¼)·2^e`，导致「倾斜足迹」。 ```go func Short(f float64) (d uint64, p int) { m, e := unpack64(f) var min uint64 z := 11 if m == 1<<63 && e > minExp { p = -skewed(e + z) min = m - 1<<(z-2) } else { if e < minExp { z = 11 + (minExp - e) } p = -log10Pow2(e + z) min = m - 1<<(z-1) } max := m + 1<<(z-1) odd := int(m>>z) & 1 pre := prescale(e, p, log2Pow10(p)) dmin := uscale(min, pre).nudge(+odd).ceil() dmax := uscale(max, pre).nudge(-odd).floor() // 后续逻辑选择正确的 d } ``` 算法返回的 `d` 至少有一位有效数字，最多可能有 17 位。对于大多数值，这个结果比 Grisu3 所需的位数更少，同时避免了 Dragonbox 复杂的特殊情况处理。 ## 性能对比：超越所有已知算法 Russ Cox 在 Apple M4 和 AMD Ryzen 9 7950X 上进行了基准测试。对比对象包括 double-conversion（Chrome 使用的库）、Gay 的 dtoa.c（1990 年和 2017 版本）、glibc 的 sprintf、Ryu、Schubfach 和 Dragonbox。 在固定宽度打印（17 位）场景中，非舍入缩放算法在两种处理器上都显著快于所有竞争者。传统的大数运算方法（如 glibc 和 double-conversion 的慢路径）在指数较大时性能急剧下降，呈现出「翼型」散点图。而非舍入缩放几乎没有慢路径，运行速度在整个指数范围内保持稳定。 在最短宽度打印场景中，竞争更加激烈。Dragonbox 的数字格式化代码非常高效，使得整体速度与非舍入缩放相当。但一旦将格式化代码排除，只比较核心转换算法，非舍入缩放就明显胜出。Russ Cox 指出 Dragonbox 的优势主要来自格式化而非算法本身。 解析场景同样令人印象深刻。非舍入缩放算法比 Eisel-Lemire（fast_float 和 Abseil 使用的算法）更快，同时代码量更少。macOS 26 的新 strtod 已经采用了 Eisel-Lemire 算法，这使得它成为唯一能与非舍入缩放竞争的 libc 实现。 ## 工程参数与监控建议 如果要在生产环境中采用这套算法，以下参数值得关注。预计算表的大小为 11KB（685 个 128 位条目），覆盖指数范围 `p ∈ [-343, 341]`，这对于 double 类型已经足够。对于 float32，可以显著缩小这个表。`log10Pow2` 的定点近似使用乘数 78913 和移位 18，`log2Pow10` 使用乘数 108853 和移位 15，这两个近似在 `int` 范围内是精确的。 粘滞位的计算是正确性的关键。在优化后的 `uscale` 实现中，当高 64 位乘法的低位全为零时，可以跳过低 64 位乘法的计算。但必须确保在这种情况下粘滞位被正确设置——Russ Cox 的代码通过检查 `(hi & ((1<