Luna Flow
简体中文

immut/dense 教程

本教程教你把一元多项式作为不可变值来计算：构建它们、进行算术、求值、复合与求导，并为长输入选择合适的乘法。

快速开始

添加模块并导入不可变门面包，它重新导出了 DensePolynomial：

moon add Luna-Flow/luna-poly@0.2.0
import {
  "Luna-Flow/luna-poly/immut",
}
test "dense quick start" {
  let p = @immut.DensePolynomial::from_coefficients([1, 2, 3])
  inspect(p, content="1 + 2x^1 + 3x^2")
  inspect(p.eval(2), content="17")
}

系数从常数项开始依次列出，因此 [1, 2, 3] 是 1+2x+3x21 + 2x + 3x^2，且 p(2)=1+4+12=17p(2) = 1 + 4 + 12 = 17。你也可以直接导入 Luna-Flow/luna-poly/immut/dense；类型是同一个。

日常任务

构建多项式

用 from_coefficients 构建整个多项式，用 constant、variable 和 monomial 构建再用运算符组合的基本组件：

test "building polynomials" {
  let x : @immut.DensePolynomial[Int] = @immut.DensePolynomial::variable()
  let two = @immut.DensePolynomial::constant(2)
  let p = x * x - two * x + @immut.DensePolynomial::monomial(0, 1)
  inspect(p, content="1 + -2x^1 + 1x^2")
  debug_inspect(p.to_coefficients(), content="[1, -2, 1]")
  inspect(@immut.DensePolynomial::from_coefficients([0, 0, 0]).is_zero(), content="true")
}

尾部零在任何地方都会被丢弃，因此 [0, 0, 0] 是零多项式，to_coefficients 总是返回最短形式。

读取系数和次数

test "reading" {
  let p = @immut.DensePolynomial::from_coefficients([5, 0, 7])
  debug_inspect(p.degree(), content="Some(2)")
  inspect(p.coefficient(0), content="5")
  inspect(p.coefficient(10), content="0")
  debug_inspect(p.leading_coefficient(), content="Some(7)")
  let zero : @immut.DensePolynomial[Int] = @immut.DensePolynomial::zero()
  debug_inspect(zero.degree(), content="None")
}

零多项式没有次数，因此 degree 返回 None 而不是 0。

进行算术而不丢失旧值

每个操作都返回新多项式；操作数保持原样：

test "value semantics" {
  let p = @immut.DensePolynomial::from_coefficients([1, 1])
  let q = p * p
  let r = q.scale(1, 2)
  inspect(p, content="1 + 1x^1")
  inspect(q, content="1 + 2x^1 + 1x^2")
  inspect(r, content="2x^1 + 4x^2 + 2x^3")
  inspect(p.pow(4), content="1 + 4x^1 + 6x^2 + 4x^3 + 1x^4")
}

scale(k, c) 乘以 c xkc\,x^k，pow(e) 是用反复平方实现的重复乘法。

求值、复合与求导

test "calculus" {
  let p = @immut.DensePolynomial::from_coefficients([1.0, -3.0, 0.0, 1.0])
  inspect(p.eval(2.0), content="3")
  let shift = @immut.DensePolynomial::from_coefficients([1.0, 1.0])
  let moved = p.substitute(shift)
  inspect(moved.eval(1.0), content="3")
  let dp = p.derivative()
  debug_inspect(dp.to_coefficients(), content="[-3, 0, 3]")
  inspect(dp.eval(1.0), content="0")
}

p.substitute(q) 是复合 p(q(x))p(q(x))，因此 moved 是 p(x+1)p(x + 1)，moved.eval(1.0) 等于 p.eval(2.0)。derivative 是形式导数；这里 p′=3x2−3p' = 3x^2 - 3 在 11 处为零。

更快地乘长多项式

* 是教科书乘积，O(mn)O(mn)。对于长操作数，调用 karatsuba，它以约 O(n1.585)O(n^{1.585}) 的代价给出相同结果：

test "karatsuba" {
  let a = @immut.DensePolynomial::from_coefficients(Array::makei(200, i => i % 5 - 2))
  let b = @immut.DensePolynomial::from_coefficients(Array::makei(150, i => i % 3 - 1))
  let fast = a.karatsuba(b)
  assert_true(fast == a * b)
  inspect(fast.length(), content="349")
}

当较短操作数少于 33 个系数时，karatsuba 直接调用 *，因此在实践中它从不会更慢。

深入了解

针对系数类型的泛型算法

用门面包重新导出的 luna-generic 约束编写算法，它们就能用于任何具备这些能力的系数类型：

fn[A : @immut.AddMonoid + Mul + Eq] square_eval(p : @immut.DensePolynomial[A], a : A) -> A {
  (p * p).eval(a)
}

test "generic coefficients" {
  inspect(square_eval(@immut.DensePolynomial::from_coefficients([1, 1]), 2), content="9")
  inspect(square_eval(@immut.DensePolynomial::from_coefficients([1U, 1U]), 2U), content="9")
  inspect(square_eval(@immut.DensePolynomial::from_coefficients([0.5, 0.5]), 1.0), content="1")
}

尽管 UInt 没有取负，UInt 系数仍然可用，因为 * 和 eval 不要求取负。

针对表示的泛型算法

DensePolynomial::ops() 把各操作打包为一个记录，因此同样的代码也能在可变表示上运行：

fn[P, A] horner_check(ops : @immut.UnivariateOps[P, A], p : P, a : A) -> A {
  ops.eval(ops.pow(p, 3), a)
}

test "ops records" {
  let p = @immut.DensePolynomial::from_coefficients([1, 1])
  let m = @mutable.DensePolynomial::from_coefficients([1, 1])
  inspect(horner_check(@immut.DensePolynomial::ops(), p, 1), content="8")
  inspect(horner_check(@mutable.DensePolynomial::ops(), m, 1), content="8")
}

不中止的错误处理

monomial、coefficient 和 scale 在幂为负时中止。它们的 _checked 形式则返回 None：

fn safe_shift(p : @immut.DensePolynomial[Int], k : Int) -> @immut.DensePolynomial[Int] {
  p.scale_checked(k, 1).unwrap_or(p)
}

test "checked" {
  let p = @immut.DensePolynomial::from_coefficients([3])
  inspect(safe_shift(p, 2), content="3x^2")
  inspect(safe_shift(p, -2), content="3")
}

通过 arithmetic 求幂

DensePolynomial 实现了 @arithmetic.PowNatChecked，因此针对 Luna-Flow/arithmetic 编写的代码可以把多项式提升到自然数次幂：

test "pow nat checked" {
  let p = @immut.DensePolynomial::from_coefficients([1, 1])
  let ctx = @arithmetic.ArithmeticContext::new(0)
  match @arithmetic.PowNatChecked::pow_nat_checked(p, 2, ctx) {
    Ok(q) => inspect(q, content="1 + 2x^1 + 1x^2")
    Err(_) => fail("pow_nat_checked never fails for polynomials")
  }
}

常见陷阱

  • 系数顺序。 数组是升序的：[a, b, c] 是 a+bx+cx2a + bx + cx^2，而不是 ax2+bx+cax^2 + bx + c。

  • 零的 degree。 它是 None。如果希望零多项式得到 0，请使用 length()。

  • 定宽溢出。 Int 系数会回绕，首项系数可能回绕为零，从而降低次数：

    test "wrapping" {
  let p = @immut.DensePolynomial::from_coefficients([1, 65536])
  inspect((p * p).degree().unwrap(), content="1")
}

  • 浮点修剪。 只有与零比较相等的系数才会被修剪。0.1 + 0.2 - 0.3 不为零，因此这样的系数会保留。

  • 导数需要 NatHomomorphism。 derivative 适用于 Float、Double 和 BigInt 系数；Int 系数没有导数。

  • 0^0。 pow(0) 对每个多项式（包括零）都返回一。

  • 打印。 to_string 会显式写出 x^1 并跳过零项；如需精确输出，请使用 to_coefficients。

后续步骤