floating_vs_decmial_x 设计

设计目标

本包在相同输入上比较 moonbitlang/x/decimal（X）与 Luna-Flow/floating/decimal_gda@0.7.1（GDA）。两个库实现的算术并不相同：X 至多保留 28 位小数并截断，GDA 则舍入到由上下文选择的有效数字精度。因此公平的比较必须先确定一个语义约定，让两个库都满足它，证明它们满足它，然后才进行测量。

API 页列出各条目，教程运行它们，测量数字见性能章节。与 DzmingLi 基准共享的方法（预言机判定、规范形式、配对统计）在 dzmingli_vs_floating 设计页中推导；本页说明不同之处。

数学背景

两种十进制模型

X 十进制数是满足 $0 \le s \le 28$ 的对 $(c, s)$ ，表示 $c \cdot 10^{-s}$ ；Decimal::new 拒绝其他标度。其运算为

\begin{aligned} a \cdot b &= \operatorname{trunc}_{28}\bigl(c_\ell c_r 10^{-(s_\ell + s_r)}\bigr) \quad\text{(exact when } s_\ell + s_r \le 28\text{)}, \\ a / b &= \Bigl\lfloor\!\Bigl\lfloor \frac{c_\ell 10^{\,28 - s_\ell + s_r}}{c_r} \Bigr\rfloor\!\Bigr\rfloor \cdot 10^{-28}, \end{aligned}

其中 $\lfloor\!\lfloor \cdot \rfloor\!\rfloor$ 是向零截断的整数除法， $\operatorname{trunc}_k$ 向零截断到 $k$ 位小数，定义见 DzmingLi 设计页。加法、减法和比较是精确的。由于 $s_\ell \le 28$ ，指数 $28 - s_\ell + s_r$ 永远不为负，所以

a / b = \operatorname{trunc}_{28}(a / b)

精确成立：X 的商就是真实商截断到 28 位小数。

在精度为 $p$ 、舍入为 Down 的上下文中，GDA 运算返回 $\operatorname{round}_p(x)$ ，即截断到 $p$ 位有效数字的精确结果；在同一上下文中，当结果能放入 $p$ 位时，quantize(y, 10^{-28}) 返回 $\operatorname{trunc}_{28}(y)$ 。

嵌套截断

关于截断的两个事实支撑着下面的证明。

引理 1。 对 $t \ge k$ 和任意实数 $x$ ， $\operatorname{trunc}_k(\operatorname{trunc}_t(x)) = \operatorname{trunc}_k(x)$ 。

证明。 设 $x \ge 0$ （负的情形对称）， $G_j = 10^{-j}\mathbb{Z}$ 。 $\operatorname{trunc}_j(x)$ 是 $G_j$ 中不超过 $x$ 的最大点。由于 $G_k \subseteq G_t$ ，点 $z = \operatorname{trunc}_k(x)$ 属于 $G_t$ 且 $z \le x$ ，所以 $z \le \operatorname{trunc}_t(x) \le x$ 。因此 $G_k$ 中不超过 $\operatorname{trunc}_t(x)$ 的最大点至少为 $z$ ，且至多为 $G_k$ 中不超过 $x$ 的最大点，即 $z$ 。 $\square$

引理 2。 对整数 $N$ 和 $A, B > 0$ ， $\lfloor\!\lfloor \lfloor\!\lfloor N / A \rfloor\!\rfloor / B \rfloor\!\rfloor = \lfloor\!\lfloor N / (AB) \rfloor\!\rfloor$ 。

证明。 对 $N \ge 0$ ，写 $N = qA + r$ ， $0 \le r < A$ ，以及 $q = uB + v$ ， $0 \le v < B$ 。则 $N = uAB + (vA + r)$ 且 $0 \le vA + r \le (B-1)A + A - 1 < AB$ ，所以 $u = \lfloor N/(AB) \rfloor$ 。向零截断关于 $N$ 是奇函数，由此得到负的情形。 $\square$

设计决策

两个语义组

问题。 对乘法和除法，一旦结果需要多于 28 位小数，两个库的原生结果就会不同，而对两种不同的计算计时毫无意义。选项。 把基准限制在两者都精确的输入上；强制 GDA 重现 X 的策略；强制 X 重现 GDA 的策略。选择。 分两个组，分别报告：ExactOverlap 限制输入，XCompatible 让 GDA 通过额外的 quantize 重现 X 的策略。理由。 X 没有可配置的上下文，所以只有 GDA 一方能够适配；而这种适配的代价正是 GDA 用户为获得 X 语义所付出的一部分。两个组带有不同的计时范围 arithmetic_only 与 semantic_equivalent_pipeline，并且从不合并。

一个预言机服务两个组

预言机实现 X 的策略：精确的加法、减法和比较，当精确积的标度超过 28 时取其 $\operatorname{trunc}_{28}$ ，以及商的 $\operatorname{trunc}_{28}$ 。对除法，记 $k = 28 + s_r - s_\ell$ ，当 $k \ge 0$ 时返回 $\lfloor\!\lfloor c_\ell 10^{k} / c_r \rfloor\!\rfloor$ ，否则返回 $\lfloor\!\lfloor \lfloor\!\lfloor c_\ell / 10^{-k} \rfloor\!\rfloor / c_r \rfloor\!\rfloor$ ，由引理 2（把 $c_r$ 的符号并入 $N$ ）它等于 $\lfloor\!\lfloor c_\ell / (10^{-k} c_r) \rfloor\!\rfloor$ 。两种情形都等于 $\operatorname{trunc}_{28}(a / b) \cdot 10^{28}$ 。

在 ExactOverlap 中，截断对每个生成的结果都是恒等映射，因此同一个预言机返回精确值：

乘法夹具使用满足 $s_\ell + s_r = 14 \le 28$ 的标度对；
除法夹具用 $2$ 、 $4$ 、 $5$ 、 $8$ 或 $25$ 去除一个整数，它们的倒数 $5 \cdot 10^{-1}$ 、 $25 \cdot 10^{-2}$ 、 $2 \cdot 10^{-1}$ 、 $125 \cdot 10^{-3}$ 和 $4 \cdot 10^{-2}$ 至多有三位小数；
加法、减法和比较按定义就是精确的。

精度约定

GDA 精度 $p$ 为 working_precision(op, ℓ, r, semantics)，不再加保护位。记 $d_\ell, d_r$ 为系数位数， $m = \max(d_\ell, d_r) + |s_\ell - s_r|$ ：

\begin{aligned} \textbf{Add/Subtract:}\quad & \text{result} < 10^{m+1} &&\Rightarrow p = m + 2 \\ \textbf{Multiply:}\quad & |c_\ell c_r| < 10^{d_\ell + d_r} &&\Rightarrow p = d_\ell + d_r + 1 \\ \textbf{Divide, ExactOverlap:}\quad & |c_\ell| \cdot \{5, 25, 2, 125, 4\} < 10^{d_\ell + 3} &&\Rightarrow p = d_\ell + d_r + 2 \ge d_\ell + 3 \\ \textbf{Compare:}\quad & \text{operands only} &&\Rightarrow p = \max(d_\ell, d_r) + 1 \end{aligned}

因此每个 ExactOverlap 结果以及量化之前的 XCompatible 积在 GDA 中都是精确的。当 $s_\ell + s_r > 28$ 时，XCompatible 积再被量化到 $10^{-28}$ ；量化后的系数位数少于精确系数，所以 quantize 成功并返回精确积的 $\operatorname{trunc}_{28}$ ，即 X 的积。

对 XCompatible 除法，精度为

p = \max(1, I) + 30, \qquad I = d_\ell - s_\ell - d_r + s_r + 1 .

$I$ 是商的整数位数的上界：

|a| < 10^{\,d_\ell - s_\ell}, \quad |b| \ge 10^{\,d_r - 1 - s_r} \quad\Rightarrow\quad |a / b| < 10^{\,d_\ell - s_\ell - d_r + s_r + 1} = 10^{I} .

divide 返回 $\operatorname{round}_p(a/b)$ 。若 $|a/b| \ge 1$ ，它至多有 $I$ 位整数，因此至少保留 $p - I \ge 30$ 位小数；若 $|a/b| < 1$ ，保留的每一位都是小数，至少保留 $p \ge 31$ 位。两种情况下都有 $\operatorname{round}_p(a/b) = \operatorname{trunc}_t(a/b)$ ，网格满足 $t \ge 30$ ，由引理 1 得

\operatorname{quantize}\bigl(\operatorname{round}_p(a/b),\ 10^{-28}\bigr) = \operatorname{trunc}_{28}\bigl(\operatorname{trunc}_t(a/b)\bigr) = \operatorname{trunc}_{28}(a/b) .

量化后的系数至多有 $I + 28 \le p - 2$ 位，因此 quantize 不会引发无效运算。28 位之外多出的两位是保护位；引理 1 并不需要它们，但它们使约定与商的最后一位如何产生无关。

这一推导假设 divide 收到的是精确的操作数 $a$ 和 $b$ 。下一节说明夹具何时打破这一假设。

已知限制：X 兼容除法中的操作数舍入

prepare_fixture 用 Decimal::from_string(text, precision=p) 解析 GDA 操作数，它按半偶舍入到 $p$ 位有效数字。对 XCompatible 除法， $p$ 取决于位数差 $I$ 而不是操作数长度，因此长于 $p$ 位的操作数会在计时的除法运行之前被舍入。由此产生两个后果。

正确性无法由构造保证。 每个操作数被舍入后相对误差至多为 $\tfrac12 10^{1-p}$ ，计算出的商与 $a/b$ 最多相差约 $|a/b| \cdot 10^{1-p} < 10^{I + 1 - p} \le 10^{-29}$ ，这可能使商越过 $10^{-28}$ 的某个倍数。例如 $a = 4\underbrace{9\cdots9}_{59}$ 和 $b = 10^{60}$ 给出 $p = 31$ ；GDA 把 $a$ 解析为 $5 \cdot 10^{59}$ 并返回 $0.5$ ，而 X 和预言机返回 $0.4999999999999999999999999999$ 。已发布的语料能通过校验，是因为它们的商远离这类边界；这是针对所记录种子的经验结果。
计时的工作量不同。 夹具把位数相同为 $D$ 的操作数配对，且 $p \le 51$ ，所以从 $D = 64$ 起，GDA 除的是至多 51 位的操作数，而 X 除的是完整的 $D$ 位操作数。因此 64 位及以上的 x_compatible 除法计时比较的并不是相同的工作量。常见位数运行（ $D \le 28 < p$ ）不受影响。

以至少 $\max(d_\ell, d_r)$ 的精度解析操作数，并在精度为 $p$ 的上下文中做除法，就能消除这两种影响。本分支上的基准代码没有改动；该限制记录在这里和性能章节中。

排除在计时之外的夹具

转换为 X 和 GDA 值、 $10^{-28}$ 量子、上下文、校验和规范化都在计时之外构造或运行。计时主体是 run_x 或 run_gda：一次公开运算，在 XCompatible 流水线中再加上 quantize 步骤。

配对统计

配对方式、相对差 $\delta$ （此处相对于 X 中位数）、 $3\,\%$ 判定阈值和加速比与 DzmingLi 基准相同，以 X 为基线：x_speedup_vs_gda 大于 $1$ 表示 X 更快。

正确性与不变量

规范形式和零容差的可靠性在 DzmingLi 设计页中证明；中立模型的代码完全相同。
ExactOverlap：由精度表以及 $\operatorname{trunc}_{28}$ 在这些结果上的恒等性，每个生成的结果在两个库中都是精确的，并等于预言机结果。
XCompatible 乘法：X、GDA 和预言机都返回精确积的 $\operatorname{trunc}_{28}$ 。
XCompatible 除法：X 和预言机对所有输入都返回 $\operatorname{trunc}_{28}(a/b)$ 。只要操作数至多有 $p$ 位有效数字，GDA 也是如此（引理 1）；更长的操作数属于上面的已知限制。
比较：X 的 Compare::compare 返回在公共标度上比较系数的符号，normalize_order 把它映射到 $\{-1, 0, 1\}$ ；GDA 的 compare 以十进制数形式返回相同的值。

被否决的方案

对所有运算使用单一的“公平”语义。 否决：对于超过 28 位小数的积和商，不存在两个库都原生实现的语义。
让 X 模仿 GDA。 否决：X 没有精度或舍入上下文，因此需要在其公开 API 之外额外重新调整标度。
以第 28 位上一个单位的容差进行比较。 否决：两边都确定性地截断，因此要求且能够做到精确一致。
每种运算一个合并分数。 否决：arithmetic_only 与 semantic_equivalent_pipeline 计时的是不同的工作。

边界

只测量 add、subtract、multiply、divide 和 compare。X 没有上下文、标志、特殊值或指数同类，因此这些都不做比较。
XCompatible 除法约定只对 GDA 能精确解析的操作数成立；参见已知限制。
HTML 语料汇总报告的总数为 validation_count + failed_count，通过数为 validation_count。Mare Mark 的 validation_count 已经包含失败，所以只要运行中有失败，汇总就会高估这两个数。已发布的运行没有失败。
Mare Mark 的实现记录写的是 moonbitlang/x@0.4.46，而模块现在依赖 moonbitlang/x@0.5.5；已发布的测量是用 0.4.46 进行的。
在当前 moonbitlang/core 的 wasm-gc 目标上，BigInt::from_string 对长输入返回错误的值；3,584 个 9 组成的字符串就已解析错误，4,096 个 9 被解析为一个 4,094 位的数。本包不使用它；测试 division precision follows the requested semantic contract 使用了它，其期望值 4097 就是从那次错误解析中记录下来的。正确值是 4099，native 和 js 目标会算出该值。
可执行程序只在 native 目标上运行，来自不同目标的结果从不合并。