yy_double.c：鲜为人知的最快浮点数转字符串算法

你从没听说过的最快 double 转 string 算法2026-08-10 Żmij 是我在之前几篇文章里写过的二进制转十进制转换库，它最初是 Schubfach 的一个优化移植版本。后来我把它的核心换成了另一种算法，该算法定义在 ibireme 的 yyjson 里的 yy_double.c 中。它没有论文，除了所在文件之外没有别的名字（我下面就叫它 yy），在 JSON 性能圈之外几乎没有什么知名度。它恰好也是最快的 dtoa 实现之一。 本文通过一个小型可视化来带你逛一遍 yy，并仔细看一个边界情况。 yy 属于 Schubfach 家族。这个家族的共同思路我在之前一篇文章里讲过：找出最短的十进制数 $\sigma \cdot 10^{e_{10}}$，使它能够往返转换回二进制浮点数 $v$——做法是把 $v$ 的舍入区间与不同间距的十进制网格求交，然后选出仍然有刻度落在该区间内的最粗网格。 yy 的诀窍在于把这件事做得非常便宜。整个算法跑在定宽整数运算上，并且只用一次与预计算 10 的幂的乘法，而经典 Schubfach 需要两到三次。 对每个二进制浮点数 $v = c \cdot 2^{e_2}$，yy 通过 $\log_{10} 2$ 的定点近似选出一个十进制指数 $e_{10}$，然后把 $v$ 重新表示到十进制尺度上： $$ \bar v \approx v \cdot 10^{-e_{10}} $$ 这里用到一张预计算的 10 的幂表 $p_{10}$，它是一个定点值，对某个二进制指数 $e_p$ 满足 $p_{10} \cdot 2^{e_p} \approx 10^{-e_{10}}$。于是 $\bar v$ 落在四个候选十进制值之间： 输出 $d_0$ 或 $u_0$ 得到的十进制数比 $d_1$ 或 $u_1$ 少一位，因为末尾的零会折叠进指数里。 和经典 Schubfach 一样，yy 在 $d_0$ 或 $u_0$ 能往返时优先选它们，否则回退到 $d_1$ 或 $u_1$。三个谓词完成这项工作，它们针对 $\bar v$ 以及它周围一个半 ulp 的带 $\delta$ 求值。第一个检查 $\bar v - \delta$ 是否够到 $d_0$： $$ \delta \ge \bar v_{10} + \varepsilon_c $$ 其中 $\bar v_{10} = \bar v \bmod 10$。第二个检查 $\bar v + \delta$ 是否够到 $u_0$： $$ \bar v_{10} + \delta \ge 10 + \eta_c $$ 第三个通过在 $\bar v$ 是否越过中点来决定更长的候选 $d_1$ 和 $u_1$ 之间选哪个： $$ \bar v \bmod 1 \ge \tfrac12 + \varepsilon_u $$ 偏置 $\varepsilon_c$、$\eta_c = 2\varepsilon_c - 1$、$\varepsilon_u$ 是很小的奇偶调整量（$0$ 或 $\pm 1$），用来在恰好打平时实现 round-half-to-even。第一个触发的谓词决定选哪个候选；如果都没有触发，答案就是 $d_1$。 $\varepsilon$ 和 $\eta$ 这些项是我为了记账自己加的，不是 yy 的：它们让我能把三个谓词写成简单统一的公式。代码里根本不调整阈值。它跑的是普通比较，只有当结果恰好落在打平点上时，才分支出去，通过测试有效数的一个低位来做舍入到偶数。 前面说的“只用一次乘法”就体现在这里：$\delta$ 不需要自己单独的乘法。$v$ 的半 ulp 是 $\tfrac12 \cdot \mathrm{ulp}(v) = 2^{e_2 - 1}$，换算到 $\bar v$ 的尺度上得到 $$ \delta = 2^{e_2 - 1} \cdot p_{10} \cdot 2^{e_p} = p_{10} \cdot 2^{e_2 + e_p - 1} $$ 所以 $\delta$ 就是把 $p_{10}$ 平移一个整数位（没有舍入，也没有第二次乘法）。舍入区间的边界就通过加减得到：$\bar v \pm \delta$。而 Schubfach 则是把 $v$、$v_l$、$v_r$ 分别乘以 $p_{10}$，这就多出两次 192 位乘法。 实际算法比这要复杂一些，还有针对不规则区间、次正规数以及数字输出循环的额外分支。上面的草图是其余部分所依附的核心思路，也是跟上这个可视化所需要的全部内容。 E4M3 是一种 8 位浮点格式（1 个符号位、4 个指数位、3 个有效数位，偏置为 7），用于近期 GPU 上的低精度 AI 推理。它只有 256 个编码，一页就能放下，这使它成为一个很好的目标，用来可视化那些在 f64 尺度上你只能选择相信的东西。我在上一篇文章里更详细地讲过这个格式。 这个走查是一个 HTML 页面，e4m3-yy.html；在新标签页里打开它。 页面从上到下带着一个值走完 yy 的流水线。顶部的主网格画出了每一个 E4M3 值，并高亮出所选值的舍入区间：