Chapter 4 Algebraic Foundations (代数的基礎)
ここから Part II で、 Arithmetic and Algebra (算術と代数) に関することが書かれる。
CGAL では、非線形な幾何的物体 (曲線や曲面など) に対する正確な計算 (exact computation) を目標としている。したがって、多項式 (polynomials), 代数的拡大 (algebraic extensions), 有限体 (finite fields) の型を表現することが重要となる。というわけで、これらの用語にピンとこない人は、この先の話は難しいかも知れない。
特に、多項式がふくまれるため、 数値型 (number type) とはこのパッケージ*1では呼ばないことにする。そんで、ある型の代数構造 (algebraic structure) と、実数に埋め込めるかどうか (実数埋め込み可能性 (real embeddable)) を区別する。さらに、明示的な混合演算を可能にする相互演算可能性 (interoperable) の概念を導入する。
らしいです。
4.2 Algebraic Structures
ここでは、CGAL が扱う環とか体といった代数構造を紹介する。インターフェースを最小にするため、群 (group) とか斜体 (skew field) とか、あんまり細かい構造や例外的な構造は扱わない。*2
Figure 4.1 のとおり、まずは整域 IntegralDomain, 一意分解整域 UniqueFactorizationDomain, Euclid 環 EuclideanRing, 体 Field という構造のコンセプト (concept) がある。コンセプトは、実装上はインターフェース (純粋仮想基底クラス) となっているようだ。
体にさらに便利な演算を付加したものが用意される。平方根演算を加えた FieldWithSqrt, k 乗根を加えた FieldWithKthRoot, さらに多項式の実根を加えた FieldWithRootOf で、それぞれ閉じた構造である*3。
整域の親に、 IntegralDomainWithoutDivision があるが、通常数学で言う整域とは逆元は定義されないので変だと思うかも知れないが、整域 IntegralDomain に割り算が要求されているわけではなく、数学的には正しく定義できる 整数除算 (integral division) が含まれているのである。整数除算って言うのはつまり、商と余りを求める計算で、 x = ap + q のような形に分解することだ。例えば、 C 言語では、整数同士の割り算 a/b は結果が整数、つまり商となり、 a%b は剰余となる。で、幾つかの整域の実装では、これらの演算が定義されていないという事実をもとに、これらを除いたコンセプトをたてておくということらしい。体は、環とは無関係になっていることにも注意。したがって、 GCD を利用するようなアルゴリズムの場合は、体 Field を使うことを最初に考えよう。
代数構造の主要な性質は Algebraic_structure_traits クラスに集約されている。trait は性質のことで、STL などでよく使われる言葉。このクラスが、ある型の性質を教えてくれる装置だとおもえばいい。この辺の詳しい話は、 Effective C++ の 「47項: 型の情報に関しては traits クラスを使おう」を読むといい。
特に、具体的なモデル AS が実現するコンセプトは、 Algebraic_structure_traits というタグ*4に記号化される。代数構造は、少なくとも、代入可能 (Assignable), コピーコンストラクト可能 (CopyConstructible), デフォルトコンストラクト可能 (DefaultConstructible), イコール比較可能 (EqualityComparable) である。さらに、すべて int からのコンストラクトが可能である。(ようするに、それぞれに対応するコンストラクタと演算子が定義されているということ) さらに使い勝手をよくするため、また、普通はあることが想定されることがおおいので、C++ 実装では基本的な算術演算子と比較演算子はすべて演算子オーバーロードが定義される。 / は体の除算に予約される。すべての単項演算 (sqrt など) や二項演算 (gcd など) はよく知られた STL のコンセプト AdaptableUnaryFunction, AdaptableBinaryFunction のモデルでなければならない。 STL をよく知らない人はわけわかかもしれないが、そのうち分かるので今はおいておいてもいいだろう。これらは、各 traits クラスのメンバになっている。これで、 STL との親和性が高く、関数をオーバーロードするのではないので名前探索 (name-lookup: C++ のコンパイル時にどの関数かを特定する作業) の不具合を回避できる。ただし、 CGAL 名前空間グローバルにも見えるようになっているが、これは後方互換のため。
4.2.1 Tags in Algebraic Structure Traits
代数のカテゴリ:
タグについて。ある型 AS にたいして、Algebraic_structure_traits は幾つかのタグを提供する。もっとも大事なのは、前述の代数構造を示す Algebraic_category である。どんな値があるかはマニュアルをみてもらうとして、代数構造コンセプトのモデルではない場合は Null_tag である。タグの値は構造体になっているようで、前述の図とおなじ継承関係を持っている。
正確性と数値敏感性 (exact and numerical sensitive):
Is_exact と Is_numerical_sensitive タグは、 Boolean_tag である。真偽の値 Tag_true, Tag_false をとるが、さすがにこれは C++ のbool で実装されているようだ。
代数構造が正確 (exact) であるとは、コンセプトに要求されるすべての演算が、2つの代数表現の比較が常に正しいように計算されることである、と書いてあるが、いまいちわからんなぁ。
数値敏感 (numerical sensitive) であるとは、その型のパフォーマンスがアルゴリズムの条件数 (condition number) に対して敏感であること。うーん。要するに計算量的なことかな。
そのあとに、この2つの概念は違う、と。例えば、 int は数値敏感ではないが、非正確である。それは、オーバーフローが起こるからである。逆に、leda_real や CORE::Expr は正確だが、内部表現で複雑なことをやっていて、数値敏感である。なお、これらのタイプについては、いずれまとめ記事を書きたい。で、正確性は、アサーションの場合分けに、数値敏感性はアルゴリズムの呼び分けに利用することを想定している。
サンプルプログラムでは、 Algebraic_category の値で特殊化*5した関数テンプレートを用意して、ぽりもるふぃっくなことをやっている。だけど、環の unit part っていうのは何だ? よくわからんが、とにかく Algebraic_category() と、デフォルトコンストラクタを呼び出して、実体を作って、それで自動的にテンプレートが選択されて実行する。関数呼び出しじゃないよ!
4.2.1 があるのに、 4.2.2 はない。ダメな体裁だなぁ、このマニュアル。
4.3 実数埋め込み可能性 (Real Embeddable)
多くの数値型は、実数の部分集合である。それらは、符号や絶対値や double approximation (なんだろ? ググると、幾つか出てくるけど) を計算できることが期待される。とくに、実数と同じ順序関係があることが期待できる。これらは、 RealComparable((RealEmbeddable の間違いでは?)) コンセプトに集約される。このコンセプトは、代数構造のコンセプトは直交である(つまり、それぞれ無関係に組み合わすことが出来る)。このコンセプトだけをモデルとする型もありうる。
このコンセプトも traits クラス指向で、 Real_embeddable_traits クラスがその性質を集約する。同じような話なので略。
ある型が IntegralDomainWithoutDivision と RealEmbeddable のモデルの場合、この型のオブジェクトによって表現される数は、算術演算と比較に関して同じである。って何が…? うーん。で、結果として、この型の環*6は整数の上位集合 (superset) で、実数の部分集合であり、標数 (characteristic) は 0 である。型が Field で RealEmbeddable なら、有理数の上位集合である。
長いので、続く。
