mutable/dense 设计

设计目标

可变的 DensePolynomial[A] 让算法可以原地构建或更新一元多项式（逐个设置系数、累加和、乘入一个累积乘积），而无需在每一步都分配新值，同时给出与 immut/dense 完全相同的数学结果。

数学背景

所表示的对象与不可变包中相同：多项式 $f = \sum_i c_i x^i \in R[x]$ ，以其修剪后的系数字存储（见 immut/dense 设计）。可变容器是保存此类值的变量。原地操作 $\mathtt{op\_inplace}(p, q)$ 是赋值 $p \leftarrow p \circ q$ ；它必须使容器保存新值的规范字。

设计决策

相同的规范形式，每次变更后恢复

不变量。 在两次公开调用之间，存储的数组从不以零系数结尾。

每个修改方法都会重新建立该不变量。当 $k \ge n$ 时，set_coefficient(k, c) 用零扩展数组，写入 $c$ ，然后修剪：若在最高位写入了 $c = 0$ ，次数会降到下一个非零系数。add_inplace 加到已有数组中并修剪，因为相消可能降低次数。mul_inplace 和 scale_inplace 赋予一个新计算出的规范数组。由于不变量成立，degree、length、== 和 compare 的含义与不可变类型完全相同。

变更是显式且有限的

只有 set_coefficient、clear、add_inplace、mul_inplace 和 scale_inplace 会改变接收者。运算符 +、-、*、一元 - 以及其他所有方法都返回新值：a + b 复制 a 并把 b 加到副本中。因此读到 p * q 的代码从不会有隐藏的副作用，变更在调用点通过名字即可看出。

别名是安全的

允许把接收者作为参数传入。对于 p.add_inplace(p)，循环逐下标计算 $c_i \leftarrow c_i + c_i$ ；在第 $i$ 步，两个操作数都在下标 $i$ 被写入之前读取它，而之后的步骤只读取更后面的下标，因此结果是 $2p$ 。mul_inplace 和 scale_inplace 在赋值之前计算出完整结果，因此 $p \leftarrow p \cdot p$ 能正确地将 $p$ 平方。

委托给不可变实现

会重复非平凡算法的操作（scale、pow、karatsuba、substitute、derivative、monomial_checked）先转换为不可变类型，调用它，再转换回来。每次转换复制系数， $O(n)$ ，其代价被算法本身所主导。因此两层在这些操作上不会产生偏差。加法、教科书乘法和 Horner 求值较短，直接在数组上实现；一致性测试检查它们与不可变版本结果一致。

转换会复制

from_immut 把不可变系数复制到新数组中，to_immut 由副本构建不可变值。用 to_immut 得到的快照无论之后可变多项式如何被修改都保持不变，交给 from_immut 的不可变值也绝不会受之后变更的影响。copy（Copyable 能力）复制数组，因此副本与原件各自独立演化。

与不可变类型的代价比较

操作	`immut/dense`	`mutable/dense`
设置一个系数	用 `from_coefficients` 重建， $O(n)$	`set_coefficient`， $O(n)$ （修剪会复制）
$p \leftarrow p + q$	新值， $O(n)$	`add_inplace`， $O(n)$ ，复用数组
$p \leftarrow p \cdot q$	$O(mn)$	$O(mn)$ ，外加一次赋值
`pow`, `substitute`, `karatsuba`	直接实现	相同，外加 $O(n)$ 的转换

set_coefficient 中的修剪会复制数组，因此在当前实现中每次调用为 $O(n)$ ；相对于不可变类型的节省来自避免每一步创建新的多项式值，以及 add_inplace 在已有存储上工作。

正确性 / 不变量

规范形式在每次公开调用之后成立；== 即多项式相等。
与 immut 一致。 对每个非修改操作，from_immut(a).op(...).to_immut() == a.op(...)；原地操作使接收者等于相应运算符的结果。
隔离。 copy、to_immut、from_immut 和 to_coefficients 从不与接收者共享存储。
别名。 p.add_inplace(p)、p.mul_inplace(p) 计算 $2p$ 和 $p^2$ 。
中止。 set_coefficient、scale_inplace、scale、coefficient 和 monomial 在幂为负时中止，与其不可变对应物相同。

被否决的替代方案

会修改操作数的运算符。 让 + 或 * 更新左操作数在循环中会更省，但会使每个算术表达式都可能产生副作用。
与不可变快照共享数组。 写时复制可使 to_immut 为 $O(1)$ ，但需要 MoonBit 数组不提供的引用跟踪。
单独的算法集合。 为可变类型重新实现 Karatsuba 或复合会使必须保持一致的代码量翻倍。

边界

没有 set_coefficient_checked；请自行验证幂，或使用不可变的 scale_checked / monomial_checked。
在另一个计算遍历多项式的 to_coefficients() 结果时修改该多项式是安全的，这仅仅是因为该结果是副本。
在程序的两个部分之间共享的可变容器会对双方同时更新；若非本意，请为每个部分提供各自的 copy()。
immut/dense 不做的一切，本包同样不做。