DOSEIの日記

技術メモ+日常ログ

Chapter 4 Algebraic Foundations (代数的基礎) 続き

メモ CGAL

id:DOSEI:20100511:p1 の続き

4.4 実数型 (Real Number Types)

CGAL のカーネルはすべて二つの実数型 (実数に埋め込み可能な数値型) のいずれかを伴う。一つは FieldNumberType で、もう一つは RingNumberType である。基本的なカーネルのオブジェクト (点・ベクトルなど) の座標はこれらの型から来る。デカルトカーネル (Cartesian kernel) の場合は FieldNumberType、同次カーネルの場合は RingNumberType。

コンセプト FieldNumberType は、 Field かつ RealEmbeddable で、コンセプト RingNumberType は IntegralDomainWithoutDivision かつ RealEmbeddable の要請を合わせたものである。代数的には、これらの型は明確に異なる構造 (structure) を構成するわけではないので、 Figure 4.1 の代数構造コンセプトの階層図には挙げられていない。

4.5 相互演算可能性 (Interoperability)

ここでは、型の相互演算可能性に関する2つのコンセプト、 ImplicitInteroperable (暗黙) と ExplicitInteroperable (明示的) を導入する。後者が基本的なコンセプトだが、より直感的な前者から説明する。

一般的な、型の混ざった演算は、オーバーロードされた演算子・関数や暗黙のコンストラクタ呼び出しで行われる。これを反映するコンセプトが ImplicitInteroperable である。しかしながら、テンプレートのコードの中で、型の混ざった算術演算 (mixed arithmetic operation) の戻り値の型 (coercion type (支配型?) ともいう) ははっきりしない場合がある。したがって、相互演算可能な型 A と B に対して CGAL::Coercion_traits::Type を通じて、 coercion type へのアクセスを提供する CGAL::Coercion_traits を導入する。

例として int と double との演算が挙げられている。この場合、結果の型 CGAL::Coercion_traits::Type は double の typedef となっているというわけである。
もう一つ、CGAL::Gmpz と CGAL::Gmpq が挙げられている。これらは、 GNU Multiple Precision Arithmetic Library のラッパー？らしい。
それから、結果の型は必ずしも引数のどちらかの方である必要はないと注意がある。

ファンクタ CGAL::Coercion_traits::Cast() にも結果の型は使われる。暗黙的相互演算可能 ExplicitInteroperable というより基本的なコンセプトである。これは、暗黙的な相互演算可能性では保証できないようは複雑なものもカバーする。
型 A, B が暗黙的相互演算可能で結果の型 C を持つとき、それらの型は C の演算構造 Algebraic_structure_traits と実数埋め込み可能 Real_embeddable_traits で提供されるあらゆる2項関数で有効な引数の型である。

例は面倒なのでスキップ（ぉ

4.6 分数

分数は、Quotient, Gmpq, mpq_class, leda_rational といったような方にはもちろん必要だけど、複合オブジェクトである Sqrt_extension (拡張平方根？ one-root number とも。 a+b√r という形の一つだけ平方根を含む数) とか多項式 Polynomial を分数に分解したい時もある。 CGAL::Fraction_traits は分母・分子の型を提供し、さらに Is_fraction という分数かどうかを表すタグも提供する。
CGAL::Rational_traits は過去の互換性のために提供されている。

一つ目の例は使い方なので読めばわかるでしょう。二つ目は、 integralization の例なんだけど、 integralization って何？ググってもわからん。というわけでコードから推定。
関数 integralize(vec, d) は、多項式をテンプレート型として与えている Fraction 型の係数の列 vec を integralize して、分母 d と、返り値で各項の分子の列を求める。たぶん、各項が整数係数になる最小の分母を計算するってことだろう。
まず、各係数を decompose で、分母・分子に分けて、 gcd でごにょごにょっと。