internal 设计

设计目标

internal 把若干表示包都需要、但不属于公开接口的代码集中在一处。目前它只包含一个函数，即每个 pow 以及每次求 $x_i^{\alpha_i}$ 所依赖的自然数幂例程。

数学背景

对单位元为 $1$ 的幺半群中的元素 $a$ 和 $e \in \mathbb{N}$，$a^e$ 是 $e$ 重乘积，$a^0 = 1$。将 $e$ 写成二进制 $e = \sum_j b_j 2^j$，得到

$$a^e = \prod_{j : b_j = 1} a^{2^j},$$

而因子 $a^{2^j}$ 通过反复平方得到。

设计决策

带显式循环不变量的二进制快速幂

pow_nat 维护三个值 state、exp 和 factor，初值分别为 $1$、$e$ 和 $a$，并保持

$$\text{state} \cdot \text{factor}^{\text{exp}} = a^e .$$

每一步在 $\text{exp} \ge 2$ 时把 $(\text{state}, \text{exp}, \text{factor})$ 替换为 $(\text{state}\cdot\text{factor}^{b}, \lfloor \text{exp}/2 \rfloor, \text{factor}^2)$，其中 $b = \text{exp} \bmod 2$。不变量得以保持：

$$\begin{aligned} \text{state}\cdot\text{factor}^{b} \cdot (\text{factor}^2)^{\lfloor \text{exp}/2 \rfloor} &= \text{state}\cdot\text{factor}^{\,b + 2\lfloor \text{exp}/2 \rfloor} \\ &= \text{state}\cdot\text{factor}^{\text{exp}} = a^e . \end{aligned}$$

循环在 $\text{exp} = 0$ 时停止并返回 state，或在 $\text{exp} = 1$ 时停止并返回 $\text{state}\cdot\text{factor}$；两种情形下不变量都给出 $a^e$。exp 每步减半，因此共有 $\lfloor \log_2 e \rfloor$ 次平方。所有相乘的值都是 $a$ 的幂，彼此可交换，因此只用到了 * 的结合律。

单位元是参数

单位元以 one~ 传入，而不是从 One 实例中获取。调用者已经知道自己的单位元（DensePolynomial::one()，系数则为 One::one()），于是该辅助函数只需要 Mul，使其约束保持最小。

正确性 / 不变量

• 对满足结合律的 *，有 pow_nat(a, e, one=u) = u · a^e；当 u 为单位元时即为 $a^e$。
• $e = 0$ 时不做乘法直接返回 one，因此 $0^0 = 1$。
• 至多 $2\lfloor\log_2 e\rfloor + 1$ 次乘法。

被否决的替代方案

• 重复乘法需要 $e - 1$ 次乘积，对多项式的幂来说太慢。
• 在每种表示上定义 trait 方法会把这个循环重复四遍。

边界

• 无法在 luna-poly 之外导入。
• 仅支持自然数指数；不支持负幂，也不支持模幂。
• 每次乘法的代价由调用者决定：对多项式而言，最后一次平方占主导。