immut/dense API

Luna-Flow/luna-poly/immut/dense は DensePolynomial[A] を提供します。これは昇順の係数ベクトルとして格納されるイミュータブルな一変数多項式です。すべての演算は正規形の新しい値を返します。正規形では末尾に零係数がなく、零多項式は空ベクトルとして格納されます。

この型は immut ファサードによって @immut.DensePolynomial として再エクスポートされており、例ではこちらを使います。アルゴリズムとそのコストは immut/dense の設計で説明しています。

型

`DensePolynomial`

DensePolynomial[A] は $c_0 + c_1 x + \dots + c_{n-1} x^{n-1}$ を、 $c_{n-1} \neq 0$ を満たす係数列 [c0, c1, ..., c(n-1)] で表します。

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$ を構築します。係数が零なら零多項式になり、負のべきは中断 (abort) します。

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`

格納されている係数の個数、すなわち次数に 1 を加えた値を返します。零に対しては 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$ の係数を返します。次数を超えるべきの係数は零として読まれます。負のべきは中断 (abort) します。

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$ を掛けます。負のべきは中断 (abort) し、係数が零なら零になります。

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 法 $(\cdots((c_{n-1} a + c_{n-2}) a + c_{n-3}) \cdots) a + c_0$ で $p(a)$ を評価します。係数が $n$ 個なら乗算 $n$ 回と加算 $n$ 回です。

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

`DensePolynomial::substitute`

$x$ を多項式 $q$ で置き換えた合成 $p(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")
}

非推奨

これらのメソッド形式はトレイト実装に由来します。インターフェースファイルからは隠されており、ソース互換性のためだけに残されています。

非推奨	代替
`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