immut/term API

Luna-Flow/luna-poly/immut/term は TermPolynomial[A] を提供します。これは (ExponentVector, A) の項の配列として格納されるイミュータブルな多変数多項式です。配列は正規形であり、単項式順序の降順にソートされ、同じ指数ベクトルを持つ項は 2 つ存在せず、係数 0 の項もありません。

この型は immut ファサードによって @immut.TermPolynomial として再エクスポートされており、例ではこちらを使います。変数はインデックスで指定し、変数 $i$ は指数ベクトルの位置 $i$ です。名前付き変数には ContextPolynomial を使ってください。設計は immut/term の設計で説明しています。

型

`TermPolynomial`

TermPolynomial[A] は $\sum_k c_k x^{\alpha_k}$ を、 $\alpha_1 \succ \alpha_2 \succ \cdots$ かつすべての $c_k \neq 0$ である項 $(\alpha_k, c_k)$ で表します。

type TermPolynomial[A] derive(Eq, @debug.Debug)
pub impl[A] @luna-generic.Zero for TermPolynomial[A]
pub impl[A : Eq + @luna-generic.Zero + @luna-generic.One] @luna-generic.One for TermPolynomial[A]
pub impl[A : Eq + @luna-generic.AddMonoid] Add for TermPolynomial[A]
pub impl[A : Eq + @luna-generic.AddMonoid + Neg] Sub for TermPolynomial[A]
pub impl[A : Eq + @luna-generic.AddMonoid + Mul] Mul for TermPolynomial[A]
pub impl[A : Eq + @luna-generic.Zero + Neg] Neg for TermPolynomial[A]
pub impl[A : Show + @luna-generic.Zero] Show for TermPolynomial[A]
pub impl[A : Eq + @luna-generic.AddMonoid + Mul + @luna-generic.One] @arithmetic.PowNatChecked for TermPolynomial[A]
pub impl[A] @core.HasArity for TermPolynomial[A]
pub impl[A] @core.HasShape for TermPolynomial[A]
pub impl[A] @core.HasTermCount for TermPolynomial[A]
pub impl[A] @core.HasTotalDegree for TermPolynomial[A]
pub impl[A] @core.IsZero for TermPolynomial[A]
pub impl[A] @core.MultivariatePolynomial for TermPolynomial[A]

構築

`TermPolynomial::from_terms`

項のリストから正規形の多項式を構築します。項をソートし、等しい指数ベクトルの係数を加え、和が 0 になったものを除きます。入力はコピーされます。入力項が $m$ 個のとき、コストは $O(m \log m)$ 回の比較です。

pub fn[A : Eq + @luna-generic.AddMonoid] TermPolynomial::from_terms(Array[(@core.ExponentVector, A)]) -> Self[A]

`TermPolynomial::from_array`

from_terms と同様ですが、各指数ベクトルを Array[UInt] で与えます（ExponentVector::from_array で変換されます）。

pub fn[A : Eq + @luna-generic.AddMonoid] TermPolynomial::from_array(Array[(Array[UInt], A)]) -> Self[A]

`TermPolynomial::zero`, `TermPolynomial::one`

空の多項式と定数 $1$ （A で $1 = 0$ なら零多項式）です。Zero::zero() と One::one() でも得られます。

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

test "construction" {
  let p = @immut.TermPolynomial::from_array([
    ([0U, 1], 3),
    ([2U], 1),
    ([1U, 0], 2),
    ([1U], -2),
    ([], 4),
  ])
  inspect(p, content="1 * x^2 + 3 * x_1 + 4")
  inspect(p.size(), content="3")
}

[1, 0] と [1] は同じ単項式なので、 $2x_0 - 2x_0$ は打ち消し合います。

問い合わせ

`TermPolynomial::to_terms`

正規形の項を新しい配列で返します。先頭項が最初です。

pub fn[A] TermPolynomial::to_terms(Self[A]) -> Array[(@core.ExponentVector, A)]

`TermPolynomial::coefficients`

to_terms の順序で係数を返します。

pub fn[A] TermPolynomial::coefficients(Self[A]) -> Array[A]

`TermPolynomial::size`, `TermPolynomial::term_count`

どちらも非零項の個数を返します。

pub fn[A] TermPolynomial::size(Self[A]) -> Int
pub fn[A] TermPolynomial::term_count(Self[A]) -> Int

`TermPolynomial::is_zero`

項がないとき true を返します。

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

`TermPolynomial::arity`

使用中の変数の個数、すなわち最長の正規形指数ベクトルの長さを返します。定数と零では 0 です。

pub fn[A] TermPolynomial::arity(Self[A]) -> Int

`TermPolynomial::total_degree`

項の全次数の最大値を返します。零の場合は None です。

pub fn[A] TermPolynomial::total_degree(Self[A]) -> UInt?

`TermPolynomial::shape`

PolynomialShape::Multivariate(arity~, term_count~) を返します。

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

test "queries" {
  let p = @immut.TermPolynomial::from_array([([1U, 2], 5), ([0U, 0, 1], 1), ([], 7)])
  inspect(p.arity(), content="3")
  debug_inspect(p.total_degree(), content="Some(3)")
  debug_inspect(p.coefficients(), content="[5, 1, 7]")
  inspect(p.to_terms()[0].0, content="xx_1^2")
}

算術演算

`TermPolynomial::add`, `TermPolynomial::sub`, `TermPolynomial::neg`

加算、減算、符号反転で、演算子 +、-、単項 - です。加算は項を連結して再正規化し、 $O((m + n) \log(m + n))$ です。符号反転は順序を保ち、 $O(m)$ です。

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

`TermPolynomial::mul`

一方のオペランドのすべての項に他方のすべての項を掛けて再正規化します。演算子 * です。項数 $m$ と $n$ に対してコストは $O(mn \log(mn))$ です。

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

`TermPolynomial::scale`

指数ベクトル $\gamma$ と係数 $c$ に対して $c\,x^\gamma \cdot p$ を返します。0 になった積は除かれます。結果は再ソートなしでソート済みのままなので、コストは $O(m)$ 回の項演算です。

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

`TermPolynomial::pow`

二分累乗法で $p^e$ を返します。pow(0) は one() です。@arithmetic.PowNatChecked からも利用できます。

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

test "arithmetic" {
  let x = @immut.TermPolynomial::from_array([([1U], 1)])
  let y = @immut.TermPolynomial::from_array([([0U, 1], 1)])
  inspect((x + y).pow(2), content="1 * x_1^2 + 2 * xx_1 + 1 * x^2")
  inspect((x + y) * (x - y), content="-1 * x_1^2 + 1 * x^2")
  let xy = @immut.ExponentVector::from_array([1U, 1])
  inspect((x + y).scale(xy, 3), content="3 * xx_1^2 + 3 * x^2x_1")
}

評価

`TermPolynomial::eval`

点 values で評価します。values[i] は変数 $i$ の値です。各項は二分累乗法で $c \prod_i a_i^{\alpha_i}$ として評価されます。values が arity() より短いと中断（abort）し、余分な値は無視されます。

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

`TermPolynomial::eval_checked`

eval と同様ですが、values.length() < arity() のとき None を返します。

pub fn[A : @luna-generic.AddMonoid + Mul + @luna-generic.One] TermPolynomial::eval_checked(Self[A], Array[A]) -> A?

test "evaluation" {
  let p = @immut.TermPolynomial::from_array([([2U], 1), ([1U, 1], 3), ([], 4)])
  inspect(p.eval([2, 5]), content="38")
  assert_true(p.eval_checked([2]) is None)
  inspect(p.eval([2, 5, 100]), content="38")
}

比較と表示

`TermPolynomial::equal`

正規形の項配列の構造的等価性で、多項式としての等価性と一致します。== です。Compare インスタンスはありません。

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

`TermPolynomial::to_string`

項を格納順に c * monomial（定数項は c のみ）として描画し、+ で連結します。零は係数の零として表示されます。単項式は ExponentVector の記法を使います。

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

ジェネリックなアクセス

`TermPolynomial::ops`

この型の MultivariateOps レコードを返します。eval_indexed は eval です。

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

test "ops" {
  let ops = @immut.TermPolynomial::ops()
  let p = ops.from_terms([(@immut.ExponentVector::from_array([1U]), 2)])
  inspect(ops.eval_indexed(ops.pow(p, 3), [1]), content="8")
}

疎な格納への変換

直接の変換メソッドはありません。項のリストを経由してください。正規化が再適用されます。

test "conversion" {
  let t = @immut.TermPolynomial::from_array([([1U], 2), ([], 1)])
  let s = @immut.SparsePolynomial::from_terms(t.to_terms())
  let back = @immut.TermPolynomial::from_terms(s.to_terms())
  assert_true(back == t)
}

非推奨

ソース互換性のために残されている、隠されたメソッド形式:

非推奨	代替
`p.not_equal(q)`	`p != q`
`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/term API

型

TermPolynomial

構築

TermPolynomial::from_terms

TermPolynomial::from_array

TermPolynomial::zero, TermPolynomial::one

問い合わせ

TermPolynomial::to_terms

TermPolynomial::coefficients

TermPolynomial::size, TermPolynomial::term_count

TermPolynomial::is_zero

TermPolynomial::arity

TermPolynomial::total_degree

TermPolynomial::shape