Luna Flow
日本語

immut/term チュートリアル

このチュートリアルでは、多変数多項式をソート済みの項リストとして扱う方法を示します。構築、項の順序どおりの読み取り、算術、点での評価、そして項をたどる小さなアルゴリズムの書き方です。

クイックスタート

moon add Luna-Flow/luna-poly@0.2.0
import {
  "Luna-Flow/luna-poly/immut",
}
test "term quick start" {
  let p = @immut.TermPolynomial::from_array([([2U], 1), ([1U, 1], 3), ([], 4)])
  inspect(p, content="3 * xx_1 + 1 * x^2 + 4")
  inspect(p.eval([2, 5]), content="38")
}

各項は (exponents, coefficient) です。[1, 1] は x0x1x_0 x_1 なので p は x02+3x0x1+4x_0^2 + 3x_0x_1 + 4 であり、p(2,5)=4+30+4=38p(2, 5) = 4 + 30 + 4 = 38 です。変数 x0x_0 は x、xix_i は x_i と表示されます。

日常的なタスク

項から構築する

項は任意の順序で、重複があっても与えられます。コンストラクタがソートし、マージし、零を取り除きます。

test "building" {
  let p = @immut.TermPolynomial::from_array([
    ([1U], 2),
    ([0U, 1], 5),
    ([1U, 0, 0], 3),
    ([0U, 1], -5),
  ])
  inspect(p, content="5 * x")
  let v = @immut.ExponentVector::from_array([0U, 0, 2])
  let q = @immut.TermPolynomial::from_terms([(v, 1), (@immut.ExponentVector::one(), -1)])
  inspect(q, content="1 * x_2^2 + -1")
}

from_terms は出来上がった ExponentVector のキーを受け取り、from_array はそれを代わりに構築します。

項を順序どおりに読む

項は先頭項から、次数付き順序で取り出されます。

test "reading terms" {
  let p = @immut.TermPolynomial::from_array([([], 1), ([1U], 1), ([0U, 1], 1), ([2U], 1)])
  let (lead, coeff) = p.to_terms()[0]
  inspect(lead, content="x^2")
  inspect(coeff, content="1")
  inspect(p.to_terms().map(t => t.0.to_string()).join(", "), content="x^2, x_1, x, 1")
  inspect(p.size(), content="4")
  debug_inspect(p.total_degree(), content="Some(2)")
}

全次数の高いものが先に来ます。同じ次数の中では添字の大きい変数が勝つので、x1x_1 が x0x_0 より先に来ます。

多項式で計算する

test "arithmetic" {
  let x = @immut.TermPolynomial::from_array([([1U], 1)])
  let y = @immut.TermPolynomial::from_array([([0U, 1], 1)])
  let one : @immut.TermPolynomial[Int] = @immut.TermPolynomial::one()
  let p = (x + y + one).pow(2)
  inspect(p.size(), content="6")
  inspect(p.eval([1, 1]), content="9")
  inspect(p - p, content="0")
}

(x0+x1+1)2(x_0 + x_1 + 1)^2 は 6 項からなり、(1,1)(1, 1) で評価すると 32=93^2 = 9 です。

安全に評価する

eval には多項式が使うすべての変数の値、すなわち少なくとも arity() 個の値が必要です。

test "evaluation" {
  let p = @immut.TermPolynomial::from_array([([0U, 0, 1], 2), ([], 1)])
  inspect(p.arity(), content="3")
  assert_true(p.eval_checked([1, 1]) is None)
  debug_inspect(p.eval_checked([0, 0, 5]), content="Some(11)")
}

点がユーザー入力から来る場合は eval_checked を使ってください。eval は配列が短いと中断 (abort) します。

単項式を掛ける

scale(γ, c) は c xγc\,x^\gamma を 1 回の線形パスで掛けます。

test "scale" {
  let p = @immut.TermPolynomial::from_array([([1U], 1), ([], 1)])
  let shifted = p.scale(@immut.ExponentVector::from_array([0U, 2]), 4)
  inspect(shifted, content="4 * xx_1^2 + 4 * x_1^2")
}

さらに進む

項をたどる

項は単純なソート済みリストなので、多くのアルゴリズムはフィルタや畳み込みになります。次は与えられた次数の斉次部分です。

fn[A : Eq + @immut.AddMonoid] homogeneous_part(
  p : @immut.TermPolynomial[A],
  degree : UInt,
) -> @immut.TermPolynomial[A] {
  @immut.TermPolynomial::from_terms(p.to_terms().filter(t => t.0.degree() == degree))
}

test "homogeneous part" {
  let p = @immut.TermPolynomial::from_array([([2U], 1), ([1U, 1], 3), ([1U], 7), ([], 4)])
  inspect(homogeneous_part(p, 2), content="3 * xx_1 + 1 * x^2")
  inspect(homogeneous_part(p, 5), content="0")
}

マップストレージに切り替える

指数による検索が必要な場合は、項リストを経由して変換します。

test "to sparse" {
  let t = @immut.TermPolynomial::from_array([([1U, 1], 3), ([], 4)])
  let s = @immut.SparsePolynomial::from_terms(t.to_terms())
  debug_inspect(s.get(@immut.ExponentVector::from_array([1U, 1])), content="Some(3)")
}

汎用コード

ストレージから独立するには MultivariateOps を受け取ります。

fn[P, A] value_of_square(ops : @immut.MultivariateOps[P, A], p : P, at : Array[A]) -> A {
  ops.eval_indexed(ops.mul(p, p), at)
}

test "generic" {
  let terms = [([1U], 1), ([0U, 1], 1)]
  let t = @immut.TermPolynomial::from_array(terms)
  let s = @immut.SparsePolynomial::from_array(terms)
  inspect(value_of_square(@immut.TermPolynomial::ops(), t, [1, 2]), content="9")
  inspect(value_of_square(@immut.SparsePolynomial::ops(), s, [1, 2]), content="9")
}

名前付き変数と代入

TermPolynomial は変数を位置で指定し、代入を持ちません。変数に名前を付けて代入するには ContextPolynomial でラップします。

test "with names" {
  let ctx = @immut.VariableContext::from_names(["x", "y"])
  let t = @immut.TermPolynomial::from_array([([1U, 1], 2)])
  let p = @immut.ContextPolynomial::from_term_polynomial(ctx, t)
  inspect(p, content="2 * x * y")
}

よくある落とし穴

  • UInt リテラル。 指数の配列は Array[UInt] です。リテラルが正しく型付けされるよう、最初の要素を 1U と書いてください。
  • 末尾の零は変数を増やしません。 [1, 0, 0] は x0x_0 であり、そのアリティは 3 ではなく 1 です。
  • 順序は辞書式ではなく次数付きです。 x1x_1 は x0x_0 より先に来て、x02x_0^2 はその両方より先に来ます。
  • 表示される単項式には区切りがありません。 xx_1 は x0x1x_0 x_1 を意味します。
  • 大きな積。 * はマージの前に mnmn 個すべての積を実体化します。非常に大きな疎な入力ではメモリを消費します。

次のステップ