internal 设计

设计目标

二进制、十进制和区间核心都把各自的困难步骤归结为精确整数运算：对齐指数、去除尾随零、按某种舍入模式做除法、将比值包络在两个二进有理数之间。internal 将这些步骤统一实现为带有明确不变量的小函数，使每个核心都按同一规则舍入，并使 consistency 测试能够针对 BigInt 预言机检查每个辅助函数。它是内部包，因此各核心可以一起修改这些辅助函数，而无需作出公开的兼容性承诺。

数学背景

带余整数除法

对于 $n \ge 0$ 和 $d > 0$ ，存在唯一的整数 $q, r$ 使得 $n = qd + r$ 且 $0 \le r < d$ （欧几里得除法）。于是 $q = \lfloor n/d \rfloor$ ，并且 $n/d$ 是整数当且仅当 $r = 0$ 。小数部分为 $r/d \in [0, 1)$ ，且

\frac{r}{d} \lesseqgtr \frac12 \iff 2r \lesseqgtr d .

舍入到整数

对于实数 $x$ 和一个舍入方向， $\circ(x)$ 是在 $\lfloor x \rfloor$ 与 $\lceil x \rceil$ 之间选出的整数：向零、向 $+\infty$ 、向 $-\infty$ 、远离零，或就近舍入且平局时取偶数候选。¹1 IEEE 754-2019 第 4.3 条定义了舍入方向属性；整数情形采用相同的定义，只是以 $\mathbb{Z}$ 作为可表示数的集合。

二进有理数包络

二进有理数（dyadic number）形如 $n \cdot 2^{-s}$ ，其中 $n \in \mathbb{Z}$ ， $s \ge 0$ 。对于实数 $x$ 和尺度 $s$ ， $x$ 附近尺度为 $s$ 的二进有理数满足 $\lfloor x 2^{s} \rfloor 2^{-s} \le x \le \lceil x 2^{s} \rceil 2^{-s}$ ，构成一个宽度至多为 $2^{-s}$ 的区间。

设计决策

分别传递绝对值与符号

round_positive_div(n, d, negative, mode) 接受 $n \ge 0$ ，并以一个标志表示真实商的符号。符号-绝对值表示正是各核心存储系数的方式，而对绝对值的定向舍入取决于符号：将 $-2.5$ 向 $-\infty$ 舍入会增大绝对值。将符号作为单独参数，使规则成为一张表，并避免了负余数——不同语言对负余数的约定各不相同。

来自共享缓存的十的幂与五的幂

十进制缩放使用 $10^{k}$ ，二进制-十进制转换使用 $5^{k}$ （因为 $10^{k} = 5^{k} 2^{k}$ ，而因子 $2^{k}$ 只是一次移位）。缓存初始包含能放入 64 位的 19 个幂，并按需扩展到 $k = 4096$ ；更大的幂在每次调用时直接计算，以免极端指数使缓存无限增长。

不经字符串计算位数

digits10 从估计值 $d_0 = \lfloor b \log_{10} 2 \rfloor + 1$ 出发（其中 $b$ 为 $|x|$ 的位长），并通过与十的幂比较来修正它。由于 $2^{b-1} \le |x| < 2^{b}$ ，真实位数 $d$ 满足

\lfloor (b-1) \log_{10} 2 \rfloor + 1 \;\le\; d \;\le\; \lfloor b \log_{10} 2 \rfloor + 1 = d_0 ,

又因为 $\log_{10} 2 < 1$ ，两个界至多相差一。因此至多只需要一次向下修正（向上的循环用于防范估计中的浮点误差），代价是常数次 BigInt 比较加上一次十的幂计算。

饱和式指数解析

split_decimal_string 在读取数字时将书写的指数限制在 $\pm 1\,500\,000\,000$ 以内。超出该值的任何指数都远在所有受支持的指数范围之外，因此该值已经上溢或下溢；限制指数可以让运算保持在 Int 范围内，而不改变任何可观察的结果。

规范化有理数

ExactRat::new 会除以 $\gcd(n, d)$ 并使分母为正。有了规范形式，派生的结构相等就是有理数相等，而这正是 semantic 在二进制与十进制表示之间比较数值时所需要的。

经认证的初等函数在工作精度 $p_k$ 下求值一个包络，当两端舍入到同一个目标数时接受结果（Ziv 策略²2 A. Ziv, “Fast evaluation of elementary mathematical functions with correctly rounded last bit”, ACM TOMS 17(3), 1991. ）；否则以更高精度重试。预算规定了如下调度

p_{k+1} = p_k + \max\bigl(32, \lfloor p_k / 2 \rfloor\bigr), \qquad k < L ,

默认 $L = 12$ 次细化。当 $p_k \ge 64$ 时即为 $p_{k+1} = \lfloor 3 p_k / 2 \rfloor$ ，即比率为 $3/2$ 的几何增长，因此 $p_L \approx p_0 (3/2)^{L}$ （当 $L = 12$ 时约为 $130\,p_0$ ）。若在精度 $p$ 下一次尝试的代价为 $C(p) \ge c\,p$ （至少线性），则所有尝试的总代价由最后一次主导：

\sum_{k=0}^{m} C(p_k) \le C(p_m) \sum_{j \ge 0} (2/3)^{j} = 3\, C(p_m) \quad \text{when } C(p_k) \le (2/3)^{m-k} C(p_m),

在几何增长阶段，对于 $\alpha \ge 1$ 的 $C(p) = c\,p^{\alpha}$ ，这一结论成立（忽略调度中的取整）。预算耗尽时以 certified_failure 报告，其中记录了目标精度与最终工作精度，而不是返回一个未经认证的值。

正确性 / 不变式

舍入表。 设 $n = qd + r$ ， $0 \le r < d$ ， $x = (-1)^{\sigma} n/d$ 。则 $|\circ(x)| \in \{q, q+1\}$ ，且仅当 $r > 0$ 时才可能为 $q + 1$ ；round_positive_div 返回 $|\circ(x)|$ ：

\begin{aligned} \text{toward zero:} &\quad |\circ(x)| = q, \\ \text{toward } +\infty: &\quad |\circ(x)| = q + [r > 0 \wedge \sigma = 0], \\ \text{toward } -\infty: &\quad |\circ(x)| = q + [r > 0 \wedge \sigma = 1], \\ \text{away from zero:} &\quad |\circ(x)| = q + [r > 0], \\ \text{nearest even:} &\quad |\circ(x)| = q + [2r > d \vee (2r = d \wedge q \text{ odd})] . \end{aligned}

证明。 $|x| = q + r/d$ 位于 $[q, q+1)$ 中。向零舍入取较小的绝对值。向 $+\infty$ 舍入对正的非整数取较大的绝对值，对负的非整数取较小的绝对值；向 $-\infty$ 舍入与之镜像对称。远离零舍入对任何非整数都取较大的绝对值。对于就近舍入，到 $q$ 的距离为 $r/d$ ，到 $q+1$ 的距离为 $1 - r/d$ ，因此 $q + 1$ 更近当且仅当 $2r > d$ ； $2r = d$ 为平局，此时取 $q, q+1$ 中的偶数者，即当且仅当 $q$ 为奇数时取 $q + 1$ 。 $\square$

round_shift(m, s, …) 是 $d = 2^{s}$ 的情形，其中 $q = m \gg s$ ， $r = m - (q \ll s)$ ，因此适用同一张表。consistency 测试在平局和定向舍入情形上依据这些公式检查这两个函数。

因子去除。 remove_factor2(sig, e) 返回 $(sig / 2^{t}, e + t)$ ，其中 $t = \operatorname{ctz}(|sig|)$ ，因此 $(sig / 2^{t}) \cdot 2^{e+t} = sig \cdot 2^{e}$ ，且新的有效数字为奇数。remove_factor10 和 trim_trailing_decimal_zeros 以同样方式保持 $c \cdot 10^{e}$ 不变，每一步去除一个因子 10；后者在 max_drop 步后停止。

包络。 certified_dyadic_fraction(n, d, s) 返回 $\ell = \lfloor n 2^{s} / d \rfloor 2^{-s}$ 和 $u = \lceil n 2^{s} / d \rceil 2^{-s}$ ；由 $\lfloor y \rfloor \le y \le \lceil y \rceil$ （其中 $y = n 2^{s}/d$ ）可得 $\ell \le n/d \le u$ 且 $u - \ell \le 2^{-s}$ ，并且 $\ell = u$ 当且仅当 $y \in \mathbb{Z}$ 。负比值的下取整按 $-\lceil |n| / d \rceil$ 计算，因此包络对两种符号都正确。certified_dyadic_div 将 $a / b = (n_a 2^{s_b}) / (n_b 2^{s_a})$ 改写为把符号移到分子上的形式，因此继承了相同的界。round_down 和 round_up 是在更小尺度上的同样的下取整与上取整，因此 $\text{round\_down}(x, s) \le x \le \text{round\_up}(x, s)$ 。

预算。 精度序列严格递增（每一步至少增加 32 位），且至多进行 limit 次细化，因此每个检查 available() 的细化循环都会终止。

中止约定。 以负指数调用 pow2、pow5、pow10，以 $n < 0$ 或 $d \le 0$ 调用 round_positive_div，以 $d = 0$ 调用 ExactRat::new，以及以负尺度调用二进有理数构造函数，都会中止：这些都是核心内部的编程错误，用户输入永远无法触及。

被否决的替代方案

借助浮点数舍入。 为舍入比值而转换为 Double 会在超过 53 位时失去精确性；所有辅助函数都保持在 BigInt 中。
带符号的带余除法。 截断除法与向下取整除法对负操作数的结果不同；符号-绝对值表示避免了这种歧义。
规范化的 CertifiedDyadic。 每次运算后都规范化需要扫描尾随零；包络使用 compare 进行比较，而它不需要规范形式。
无界的幂缓存。 病态的指数会在整个进程生命周期内保留巨大的 BigInt 值。

边界

不提供浮点格式、上下文或标志：核心在这些辅助函数之上构建它们。
split_decimal_string 不做十进制字符串格式化，也不处理特殊值（inf、nan）。
不提供公开的稳定性保证：该包只能在 Luna-Flow/floating 内部导入。
幂缓存是进程范围的可变状态，也是该包中唯一的状态；它们绝不会改变任何结果。

IEEE 754-2019 第 4.3 条定义了舍入方向属性；整数情形采用相同的定义，只是以 $\mathbb{Z}$ 作为可表示数的集合。 ↩
A. Ziv, “Fast evaluation of elementary mathematical functions with correctly rounded last bit”, ACM TOMS 17(3), 1991. ↩