immut/dense API

Luna-Flow/luna-poly/immut/dense 提供 DensePolynomial[A]：一种不可变的一元多项式，以升幂系数向量存储。每个操作都返回规范形式的新值：没有末尾的零系数，零多项式存储为空向量。

该类型由 immut 门面包重新导出为 @immut.DensePolynomial，示例中使用的就是它。算法及其代价见 immut/dense 设计。

类型

`DensePolynomial`

DensePolynomial[A] 用系数 [c0, c1, ..., c(n-1)] 表示 $c_0 + c_1 x + \dots + c_{n-1} x^{n-1}$ ，其中 $c_{n-1} \neq 0$ 。

type DensePolynomial[A] derive(Compare, Eq, @debug.Debug)
pub impl[A] @luna-generic.Zero for DensePolynomial[A]
pub impl[A : Eq + @luna-generic.Zero + @luna-generic.One] @luna-generic.One for DensePolynomial[A]
pub impl[A : Eq + @luna-generic.AddMonoid] Add for DensePolynomial[A]
pub impl[A : Eq + @luna-generic.AddMonoid + Neg] Sub for DensePolynomial[A]
pub impl[A : Eq + @luna-generic.AddMonoid + Mul] Mul for DensePolynomial[A]
pub impl[A : Eq + @luna-generic.Zero + Neg] Neg for DensePolynomial[A]
pub impl[A : Show + Eq + @luna-generic.Zero] Show for DensePolynomial[A]
pub impl[A : Eq + @luna-generic.AddMonoid + Mul + @luna-generic.One] @arithmetic.PowNatChecked for DensePolynomial[A]
pub impl[A] @core.HasDegree for DensePolynomial[A]
pub impl[A] @core.HasLength for DensePolynomial[A]
pub impl[A] @core.HasShape for DensePolynomial[A]
pub impl[A] @core.IsZero for DensePolynomial[A]
pub impl[A] @core.UnivariatePolynomial for DensePolynomial[A]

每个操作只要求它实际用到的系数能力：加法需要 Eq + AddMonoid，取负需要 Eq + Zero + Neg，乘法需要 Eq + AddMonoid + Mul，依此类推。凡是结果需要去除末尾零的地方，都需要 Eq 和 Zero。

构造

`DensePolynomial::from_coefficients`

用给定的升幂系数构造多项式，并去掉末尾的零。数组会被复制。

pub fn[A : Eq + @luna-generic.Zero] DensePolynomial::from_coefficients(Array[A]) -> Self[A]

`DensePolynomial::constant`

构造常数多项式 $c$ ；constant(0) 是零多项式。

pub fn[A : Eq + @luna-generic.Zero] DensePolynomial::constant(A) -> Self[A]

`DensePolynomial::variable`

构造多项式 $x$ 。

pub fn[A : Eq + @luna-generic.Zero + @luna-generic.One] DensePolynomial::variable() -> Self[A]

`DensePolynomial::monomial`

由 power $k$ 和 coefficient $c$ 构造 $c\,x^k$ 。系数为零时得到零多项式；幂为负时中止。

pub fn[A : Eq + @luna-generic.Zero] DensePolynomial::monomial(Int, A) -> Self[A]

`DensePolynomial::monomial_checked`

与 monomial 相同，但幂为负时返回 None。

pub fn[A : Eq + @luna-generic.Zero] DensePolynomial::monomial_checked(Int, A) -> Self[A]?

`DensePolynomial::zero`, `DensePolynomial::one`

加法单位元和乘法单位元，也可通过 Zero::zero() 和 One::one() 获得。若系数类型满足 $1 = 0$ ，则 one() 是零多项式。

pub fn[A] DensePolynomial::zero() -> Self[A]
pub fn[A : Eq + @luna-generic.Zero + @luna-generic.One] DensePolynomial::one() -> Self[A]

test "construction" {
  let p = @immut.DensePolynomial::from_coefficients([1, 2, 3, 0, 0])
  debug_inspect(p.to_coefficients(), content="[1, 2, 3]")
  let x : @immut.DensePolynomial[Int] = @immut.DensePolynomial::variable()
  inspect(x, content="1x^1")
  inspect(@immut.DensePolynomial::monomial(3, 5), content="5x^3")
  assert_true(@immut.DensePolynomial::monomial_checked(-1, 5) is None)
  let zero : @immut.DensePolynomial[Int] = @immut.DensePolynomial::zero()
  assert_true(@immut.DensePolynomial::constant(0) == zero)
}

查询

`DensePolynomial::to_coefficients`

返回一个新数组，包含规范系数，低次在前；零多项式返回 []。

pub fn[A] DensePolynomial::to_coefficients(Self[A]) -> Array[A]

`DensePolynomial::length`

返回存储的系数个数，即次数加一；零多项式返回 0。

pub fn[A] DensePolynomial::length(Self[A]) -> Int

`DensePolynomial::degree`

返回 Some(length() - 1)；对零多项式返回 None。

pub fn[A] DensePolynomial::degree(Self[A]) -> Int?

`DensePolynomial::is_zero`

对零多项式返回 true。

pub fn[A] DensePolynomial::is_zero(Self[A]) -> Bool

`DensePolynomial::coefficient`

返回 $x^k$ 的系数；超出次数的幂读作零。幂为负时中止。

pub fn[A : @luna-generic.Zero] DensePolynomial::coefficient(Self[A], Int) -> A

`DensePolynomial::coefficient_checked`

幂为负时返回 None，否则返回 Some(coefficient(k))。

pub fn[A : @luna-generic.Zero] DensePolynomial::coefficient_checked(Self[A], Int) -> A?

`DensePolynomial::leading_term`, `DensePolynomial::leading_coefficient`

leading_term 返回最高非零项的 (degree, coefficient)，leading_coefficient 只返回其系数；对零多项式两者都返回 None。

pub fn[A] DensePolynomial::leading_term(Self[A]) -> (Int, A)?
pub fn[A] DensePolynomial::leading_coefficient(Self[A]) -> A?

`DensePolynomial::shape`

返回 PolynomialShape::Univariate(length~)。

pub fn[A] DensePolynomial::shape(Self[A]) -> @core.PolynomialShape

test "queries" {
  let p = @immut.DensePolynomial::from_coefficients([4, 0, -1])
  inspect(p.length(), content="3")
  debug_inspect(p.degree(), content="Some(2)")
  inspect(p.coefficient(1), content="0")
  inspect(p.coefficient(9), content="0")
  assert_true(p.coefficient_checked(-1) is None)
  debug_inspect(p.leading_term(), content="Some((2, -1))")
  let zero : @immut.DensePolynomial[Int] = @immut.DensePolynomial::zero()
  debug_inspect(zero.degree(), content="None")
  assert_true(zero.is_zero())
}

算术

`DensePolynomial::add`, `DensePolynomial::sub`, `DensePolynomial::neg`

逐系数的加法、减法和取负，即运算符 +、- 和一元 -。结果会去除末尾零，因此首项相消时次数会降低。对长度为 $m$ 和 $n$ 的操作数，代价为 $O(\max(m, n))$ 。

pub fn[A : Eq + @luna-generic.AddMonoid] DensePolynomial::add(Self[A], Self[A]) -> Self[A]
pub fn[A : Eq + @luna-generic.AddMonoid + Neg] DensePolynomial::sub(Self[A], Self[A]) -> Self[A]
pub fn[A : Eq + @luna-generic.Zero + Neg] DensePolynomial::neg(Self[A]) -> Self[A]

`DensePolynomial::mul`

按教科书式卷积 $(fg)_k = \sum_{i+j=k} f_i g_j$ 相乘，即运算符 *。代价为 $O(mn)$ 次系数乘法。

pub fn[A : Eq + @luna-generic.AddMonoid + Mul] DensePolynomial::mul(Self[A], Self[A]) -> Self[A]

`DensePolynomial::karatsuba`

使用 Karatsuba 分治算法相乘，结果等于 self * other。当较短的操作数至多有 32 个系数时退回到 *；超过此规模时，对长度为 $n$ 的操作数代价为 $O(n^{\log_2 3}) \approx O(n^{1.585})$ 。由于中间乘积通过减法得到，它需要 Neg。

pub fn[A : Eq + @luna-generic.AddMonoid + Mul + Neg + @luna-generic.One] DensePolynomial::karatsuba(Self[A], Self[A]) -> Self[A]

`DensePolynomial::scale`

返回 $c\,x^k \cdot p$ ：将系数上移 power $k$ 位，并乘以 coefficient $c$ 。幂为负时中止；系数为零时得到零。

pub fn[A : Eq + @luna-generic.Zero + Mul] DensePolynomial::scale(Self[A], Int, A) -> Self[A]

`DensePolynomial::scale_checked`

与 scale 相同，但幂为负时返回 None。

pub fn[A : Eq + @luna-generic.Zero + Mul] DensePolynomial::scale_checked(Self[A], Int, A) -> Self[A]?

`DensePolynomial::pow`

用二进制快速幂计算 $p^e$ ，至多进行 $2\lfloor \log_2 e \rfloor + 1$ 次乘法。pow(0) 是 one()，对零多项式也是如此。

pub fn[A : Eq + @luna-generic.AddMonoid + Mul + @luna-generic.One] DensePolynomial::pow(Self[A], UInt) -> Self[A]

同一函数也可通过 @arithmetic.PowNatChecked::pow_nat_checked(p, e, context) 调用，它总是返回 Ok 并忽略上下文。

test "arithmetic" {
  let p = @immut.DensePolynomial::from_coefficients([1, 1])
  let q = @immut.DensePolynomial::from_coefficients([1, -1])
  inspect(p + q, content="2")
  inspect(p * q, content="1 + -1x^2")
  inspect(p - p, content="0")
  inspect(p.scale(2, 3), content="3x^2 + 3x^3")
  assert_true(p.scale_checked(-1, 3) is None)
  inspect(p.pow(3), content="1 + 3x^1 + 3x^2 + 1x^3")
  let big = @immut.DensePolynomial::from_coefficients(Array::makei(40, i => i % 3 - 1))
  assert_true(big.karatsuba(big) == big * big)
}

求值与微积分

`DensePolynomial::eval`

用 Horner 法则求 $p(a)$ ，即 $(\cdots((c_{n-1} a + c_{n-2}) a + c_{n-3}) \cdots) a + c_0$ ：对 $n$ 个系数需要 $n$ 次乘法和 $n$ 次加法。

pub fn[A : @luna-generic.AddMonoid + Mul] DensePolynomial::eval(Self[A], A) -> A

`DensePolynomial::substitute`

返回复合 $p(q)$ ，即把 $x$ 替换为多项式 $q$ ，在多项式上使用 Horner 法则计算。

pub fn[A : Eq + @luna-generic.AddMonoid + Mul] DensePolynomial::substitute(Self[A], Self[A]) -> Self[A]

`DensePolynomial::derivative`

返回形式导数 $\sum_{i \ge 1} i\,c_i\,x^{i-1}$ 。因子 $i$ 通过 @luna-generic.NatHomomorphism::from_nat 映射到系数类型中，因此在特征 $p$ 下 $x^p$ 的导数为零。luna-generic 为 Float、Double 和 BigInt 实现了 NatHomomorphism，所以只有这些系数类型具有导数；Int 系数没有。

pub fn[A : @luna-generic.NatHomomorphism + Eq + @luna-generic.Zero + Mul] DensePolynomial::derivative(Self[A]) -> Self[A]

test "evaluation and calculus" {
  let p = @immut.DensePolynomial::from_coefficients([1, 2, 3])
  inspect(p.eval(2), content="17")
  let shift = @immut.DensePolynomial::from_coefficients([1, 1])
  inspect(p.substitute(shift), content="6 + 8x^1 + 3x^2")
  let f = @immut.DensePolynomial::from_coefficients([5.0, 0.0, 1.0, 2.0])
  debug_inspect(f.derivative().to_coefficients(), content="[0, 2, 6]")
}

比较与打印

`DensePolynomial::equal`

规范系数向量的结构相等，也就是多项式相等。即 ==。

pub fn[A : Eq] DensePolynomial::equal(Self[A], Self[A]) -> Bool

`DensePolynomial::compare`

供有序容器使用的结构性全序：较短（次数较低）的多项式在前，然后从常数项起逐个比较系数。它与环运算不相容。

pub fn[A : Compare] DensePolynomial::compare(Self[A], Self[A]) -> Int

`DensePolynomial::to_string`

按升幂输出非零项，常数项写作 c，其余写作 cx^k，用 + 连接；零输出为系数零。

pub fn[A : Show + Eq + @luna-generic.Zero] DensePolynomial::to_string(Self[A]) -> String

test "comparison and printing" {
  let a = @immut.DensePolynomial::from_coefficients([9])
  let b = @immut.DensePolynomial::from_coefficients([0, 1])
  assert_true(a < b)
  inspect(@immut.DensePolynomial::from_coefficients([0, -2, 0, 1]), content="-2x^1 + 1x^3")
}

泛型访问

`DensePolynomial::ops`

返回该类型的 UnivariateOps 记录，其中连接了 zero、one、from_coefficients、to_coefficients、coefficient、coefficient_checked、eval、+、*、scale、scale_checked 和 pow。

pub fn[A : Eq + @luna-generic.AddMonoid + Mul + @luna-generic.One] DensePolynomial::ops() -> @core.UnivariateOps[Self[A], A]

test "ops" {
  let ops = @immut.DensePolynomial::ops()
  let p = ops.from_coefficients([1, 1])
  inspect(ops.eval(ops.mul(p, p), 3), content="16")
}

已弃用

这些方法形式来自 trait 实现。它们在接口文件中被隐藏，仅为源码兼容而保留。

已弃用	替代方案
`p.not_equal(q)`	`p != q`
`p.op_lt(q)`, `op_le`, `op_gt`, `op_ge`	`<`, `<=`, `>`, `>=`
`p.output(logger)`	`to_string` 或字符串插值
`p.to_repr()`	`Repr(p)` 或 `debug_inspect`
`p.pow_nat_checked(e, ctx)`	`@arithmetic.PowNatChecked::pow_nat_checked(p, e, ctx)` 或 `p.pow(e)`

immut/dense API

类型

DensePolynomial

构造

DensePolynomial::from_coefficients

DensePolynomial::constant

DensePolynomial::variable

DensePolynomial::monomial

DensePolynomial::monomial_checked

DensePolynomial::zero, DensePolynomial::one

查询

DensePolynomial::to_coefficients

DensePolynomial::length

DensePolynomial::degree

DensePolynomial::is_zero

DensePolynomial::coefficient

DensePolynomial::coefficient_checked

DensePolynomial::leading_term, DensePolynomial::leading_coefficient

DensePolynomial::shape

算术

DensePolynomial::add, DensePolynomial::sub, DensePolynomial::neg

DensePolynomial::mul

DensePolynomial::karatsuba

DensePolynomial::scale

DensePolynomial::scale_checked

DensePolynomial::pow