internal の設計

設計目標

internal は、複数の表現パッケージが必要とするものの公開インターフェースには含めないコードを 1 か所にまとめます。現在は関数が 1 つだけで、すべての 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 は 3 つの値 state、exp、factor を保持し、初期値はそれぞれ $1$、$e$、$a$ で、次を維持します。

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

$\text{exp} \ge 2$ の各ステップは、$b = \text{exp} \bmod 2$ として $(\text{state}, \text{exp}, \text{factor})$ を $(\text{state}\cdot\text{factor}^{b}, \lfloor \text{exp}/2 \rfloor, \text{factor}^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$ 回の積) は、多項式のべきには遅すぎます。
• 各表現に トレイトメソッド を置くと、ループが 4 回重複します。

境界

• luna-poly の外からはインポートできません。
• 自然数の指数のみです。負のべきやべき剰余はありません。
• 各乗算のコストは呼び出し側に依存します。多項式の場合は最後の二乗が支配的です。