Rational Numbers

コンテンツ

1. Class rational synopsis
2. 理論的根拠
3. 背景
4. 基本要素となる整数型の要件
5. インターフェイス
   • ユーティリティ関数
   • コンストラクタ
   • 算術演算子
   • 入出力
   • In-place assignment
   • 型変換
   • 分数表現（Numerator and Denominator）
6. パフォーマンス
7. 例外
8. 内部表現
9. デザインノート
   • 最小の実装（Minimal Implementation）
   • 範囲制限された整数型（Limited-range integer types）
   • 浮動小数点データからの型変換
   • 絶対値
10. リファレンス
11. History and Acknowledgements

Class rational synopsis

#include <boost/rational.hpp>

namespace boost {

template <typename I> I gcd(I n, I m);
template <typename I> I lcm(I n, I m);

class bad_rational;

template<typename I> class rational {
    typedef I int_type;

    // コンストラクタ
    rational();          // ゼロ
    rational(I n);       // n/1 （つまり、整数値の n）
    rational(I n, I d);  // n/d に等しい

    // コピーコンストラクタと代入演算子

    // 基本要素となる整数型からの代入
    rational& operator=(I n);

    // in place 代入
    rational& assign(I n, I d);

    // （内部の）表記へのアクセス
    I numerator() const;
    I denominator() const;

    // 以下の演算子に加えて、継承した演算子が使用可能である。
    // operators.hpp を参照のこと。

    // 数値演算
    rational& operator+= (const rational& r);
    rational& operator-= (const rational& r);
    rational& operator*= (const rational& r);
    rational& operator/= (const rational& r);

    // 整数型との数値演算
    rational& operator+= (I i);
    rational& operator-= (I i);
    rational& operator*= (I i);
    rational& operator/= (I i);

    // インクリメントとデクリメント
    const rational& operator++();
    const rational& operator--();

    // 否定演算
    bool operator!() const;

    // 比較演算
    bool operator< (const rational& r) const;
    bool operator== (const rational& r) const;

    // 整数型との比較演算
    bool operator< (I i) const;
    bool operator> (I i) const;
    bool operator== (I i) const;
}

// 単項演算子
template <typename I> rational<I> operator+ (const rational<I>& r);
template <typename I> rational<I> operator- (const rational<I>& r);

// 整数型（と型コンパチブルな型）から有理数クラスを引く／割る演算子
// Reversed order operators for - and / between (types convertible to) I and rational
template <typename I, typename II> inline rational<I> operator- (II i, const rational<I>& r);
template <typename I, typename II> inline rational<I> operator/ (II i, const rational<I>& r);

// 絶対値
template <typename I> rational<I> abs (const rational<I>& r);

// 入出力
template <typename I> std::istream& operator>> (std::istream& is, rational<I>& r);
template <typename I> std::ostream& operator<< (std::ostream& os, const rational<I>& r);

// 型変換
template <typename T, typename I> T rational_cast (const rational<I>& r);

理論的根拠

「数」の分類には種々のものがある。 最も基本的なものとしては、自然数（非負の整数）、そして、整数と実数がある。 こういった数は（数学的な厳密性は犠牲にされているものの）Ｃ＋＋において unsigned int, int, float （そして、おのおのに対応する異なったサイズのデータ型）として、組み込まれている。

Ｃ＋＋標準ライブラリは、さらに複素数型の機能を提供している。

本ライブラリでは、さらに、有理数クラス の機能を提供する。

実際には、本ライブラリにおける 有理数クラス は、標準ライブラリにおける 複素数 型と同じくテンプレートベースで提供される。

背景

数学的に言えば、有理数とは分数――２つの整数の比で表される数のことである。 このため、有理数の範囲では表現できない実数値（実数は、２の平方根など分数で表現できない数も表すことができる）も存在する。

コンピュータにおいては数学的な概念を厳密に表現することはできず、数値の扱いにおいて、「妥協」が存在する。 整数型では値を表現できる範囲に制限（しばしば、32bit幅）が存在し、実数値の近似では精度の限界が存在する。 こういった、「妥協」は計算の目的に応じて採用されている。 整数演算は表現範囲が狭いが正確な計算が可能であり、一方、実数演算であれば、精度を犠牲にしなければならないものの、表現できる数値の範囲はずっと広くなる。

有理数ライブラリはこの表現範囲と精度の制限に対して、整数や実数で行われているのとは別の方法を実現するものである。 有理数による演算は正確に行われる。 依然として数値の表現範囲に限界があるものの、（通分が行われた後の）分子と分母のデータ長が、テンプレートで使用された整数型のデータ長の範囲である限りにおいては、数値を表現することができる。 しかしながら、分母や分子の値がテンプレートで与えられた整数型の範囲を超える場合には、演算結果は未定義となる。

有理数クラスは、プログラマが、基本要素となる整数型を適切に選択することによって、オーバーフローの発生を制御できるようにテンプレートクラスとして実装されている。 たとえば、テンプレートで無限精度の整数型（に類する）クラスが与えられれば、有理数クラスの中でオーバーフローは発生することがなく、あらゆる環境に於いて正確な演算結果が得られる。

基本要素となる整数型の要件

有理数クラスは、単一の型パラメータ I をとるテンプレートクラスである。 この単一の整数型パラメータは、有理数クラスを構成する 基本要素 となる。 C++ のすべての汎整数型は、型パラメータ I として使用できる。 ユーザー定義の整数型も同様に使用できるが、ユーザー定義型を使用する場合には、ユーザー定義型の演算速度や能力が有理数クラスの演算に大きく影響することを考慮する必要がある。 （考慮すべき点はしばしば複雑であり――そのため、詳細は後述する パフォーマンス の項目を参照すること）

補足：boost ライブラリは無限精度整数型をサポートする予定である。 この無限精度整数型は、有理数クラスの基本要素として利用できるものである。

ユーザー定義の整数型を有理数クラスの基本要素として利用する場合には、以下の関数を準備する必要がある。

• 代入
• デフォルトコンストラクタ
• 比較演算子 ==
• 比較演算子 <

Fさらに、基本要素として利用できる型は、整数型に類似していて、任意の２つのインスタンスの間で以下の演算が、整数型として自然に定義されていなければならない。

• n + m
• n - m
• n * m
• n / m （結果は切り捨てられること。また、n, m が正の場合には結果も正であること）
• n % m （n, m が正の場合には結果も正であること）
• 上記の演算結果が代入できること
• +n, -n

ユーザー定義整数型に、０および、１ に相当する要素が存在でき。 それらは、I(0) I(1) でそれぞれ、生成できなければならない。

補足：この条件は必ずしも int 型と暗黙の型変換が可能であることを意味しない。 explicit 修飾されたコンストラクタが存在してもよい。

ユーザー定義整数型として、符号無しのものも許される。 この場合、生成された有理数クラスもまた符号無しとなる。 この場合には、引き算によるアンダーフローが発生した場合でも結果は負になることはなく、予測されない結果となる。

• rational_cast<T>(rational<I>) が可能か否かは、I から T への sataic_cast が可能かどうかと等価である。 また、x, y がいずれも T 型であるときに、x/y は有効である。
• 入出力のための演算子は、型パラメータ I における入出力演算子の動作と同様に動作する。

インターフェイス

ユーティリティ関数

ユーティリティ関数として、以下の２個が提供される。

これらのユーティリティ関数は、有理数クラスの基本要素となる整数型 I に対して定義される。 この際、I において以下のオペレータが定義されていなければならない。

=, +=, *=, /=, %, < そして、I(0) によって、ゼロ元にアクセスできること。

補足：将来的にこの２つの関数は、別途「ユーティリティライブラリ」のなかで定義される可能性がある

コンストラクタ

有理数クラスは、２つの整数値（分子、分母）の組み合わせ、あるいは、単一の整数値から生成される。 また、デフォルトコンストラクタは、値がゼロであるような有理数を生成する。 コンストラクタとしては、以下の形が有効である。

I n, d;
rational<I> zero;
rational<I> r1(n);
rational<I> r2(n, d);

単一の整数値を取るコンストラクタは、explicit 修飾されて いない 。 このため、基本要素となる整数型から有理数クラスへの暗黙の型変換が発生しうる。

算術演算子

有理数クラスにおいては、以下に示す標準的な算術演算子が定義される。

+    +=
-    -=
*    *=
/    /=
++   --    前置・後置の両方の演算子）
==   !=
<    >
<=   >=

入出力

入出力のために、<< および、>> のそれぞれの演算子が定義される。 有理数クラスの外部での表現形（The external representation）は、/ で区切られた２つの整数値である。 入力の場合、/ と整数値の間にホワイトスペースが存在してはならない。 （入力においては、整数値の後間にホワイトスペースが存在せずに、/ が続き、さらにその後にもホワイトスペースが存在せず）２番目の整数値が現れなければならない）整数値の表現形は基本要素となる整数型によって定義される形である。

In-place assignment

有理数クラスの任意のインスタンス rational<I> r に対して、r.assign(n, m)は、一時インスタンスを生成しないため、r = rational<I&>(n, m); より高速に処理を行うことができる。 この機能は、基本要素となる整数型がＣ＋＋組み込みの場合であればそれほど有効ではないかもしれないが、たとえば、無限精度整数型の上に構成された有理数クラスの場合には有効である。

型変換

有理数クラスは暗黙には他の いかなる型にも変換されない 。 しかしながら、明示的な型変換のためには、関数、 rational_cast<T>(r) を提供する。 これは。

rational r(22,7);
double nearly_pi = boost::rational_cast<double>(r);

に示すように使用することができる。

関数 rational_cast<T> は、分母と分子の両方が安全に T にキャストできない場合、あるいは、（T にキャストした後で）分子／分母 の（割り算の値が）T の範囲で正しく表現できない場合には、未定義動作となる。

本質的には、型変換の際に数字としてみた値が保存され、また、演算結果は理にかなったものでなければならないということである。 ここに述べるような制約が不都合である場合には、別途ユーザー定義の型変換を行った方がより適切であろう。

実装上の注意：

ratinal_cast<T> の具体的な実装は、

template <typename Float, typename Int>
Float rational_cast(const rational<Int>& src)
{
    return static_cast<Float>(src.numerator()) / src.denominator();
}

である。 しかしながら、この実装に依存するようなプログラムを書いてはならない。

分数表現（Numerator and Denominator）

直接的に有理数クラスの内部表現にアクセスするためには２つの関数、 numerator() と、 denominator() を使用する。

この２つの関数を使用することで、ユーザーは有理数を取り扱う上の任意の機能を追加することができる。 とりわけ、上で示した rational_cast の実装がうまく動かない場合――基本要素として、無限精度の整数型を使用している場合にはありそうだが――に、ユーザーがもっと適切な浮動小数点型への型変換関数を、別途準備できることに注意したい。

パフォーマンス

有理数クラスは、基本要素となる整数型が、組み込みの整数型と“類似の”振る舞いをすることを暗黙のうちに想定している。 この基本要素となる整数型の振る舞いを明文化したものが、前述した 基本要素となる整数型の要件 である。 しかしながら、振る舞いの他にも、演算のパフォーマンスもまた組み込みの整数型と同等であることも、暗黙のうちに想定されている。

有理数クラスにおける演算のパフォーマンスを精密に保証することはできない。 その上、パフォーマンスにおける議論は（標準クラスライブラリに於いても同様であるが）ユーザーに詳細な演算コストを提供するためには、有用なものではない。 その代わりに、このセクションでは有理数クラスの特性に関する一般的な情報を提供する。

ここでは、<boost/rational.hpp> に定義された演算子と、その演算子の実行にかかるコストの非公式なリストを示す。 このリストの内容は、現時点の実装に依存しているものであり、将来変更される可能性があるととに注意されたし。

• コンストラクタの実行は、本質的には２つの要素を基本要素の型で生成し、約分を行うことである。
• インクリメントとデクリメントは、基本要素の型における加算および減算と同じ程度の負荷である。
• 等号および、不等号の比較は、基本要素の型における同一の比較と同じ程度の負荷である。
• I/O の負荷は低くはない。 しかしながら、本質的には I/O の動作自体の時間がほとんどである。
• gcd() 関数は、本質的には剰余演算の繰り返しである。 このほかに、コンストラクタ・代入・０との比較が行われるが、これらの負荷は剰余演算に比べると、取るに足らないものである。
• lcm() 関数は、本質的に gcd() を算出した後、２回の乗算と（１回の）除算を行うものである。
• 加算と減算は複雑である。 加算と減算には基本要素となる整数型上で、平均して２回の gcd() 、３回の除算、３回の乗算と１回の加算が必要である。
• 乗算と除算には、２回の gcd() 、２回の乗算、そして、４回の除算が必要である。
• 比較演算子の実行には、最悪の場合、２回の gcd() , ２回の乗算、４回の除算、そして比較が必要である。 しかしながら、int タイプにおける比較演算のコストが低い（そして、０との比較はさらに低コストである）と仮定すると、比較演算のオーバーヘッドを下げることのできる特別なケースがいくつか存在する。 特に、 == と != の実行時間は、基本要素となる整数型の比較時間程度のコストで終了する。
• 残りの基本的な演算は、約分である。 約分はコンストラクタの起動時と、内部での代入の際に暗黙のうちに実行される。 その他の演算結果も基本要素となる整数型の範囲に収まるように注意深く約分される。 約分のコストは、 gcd() １回と、除算が２回分に相当する。

上記の議論の際に、注意すべきことは、基本要素となる整数型の演算は“常識的な”パフォーマンスで実行できることが暗黙のうちに仮定されているということ――すなわち、演算コストがかかるのは乗算・除算・剰余の計算であり、加算と減算のコストは比較的安価だと仮定されているということである。 コンストラクタ（整数値０，１から生成される場合）と代入のコストはさらに安価だと仮定しているが、それでも、本有理数クラスライブラリにおいて、不要なコンストラクタやコピーが発生しないような配慮は行っている。 また、比較（特に０に対する比較）の演算コストも低いと仮定している

以上のような仮定に合致しない整数型は、有理数クラスの基本要素としては有用ではない。 殊にパフォーマンスの点では、ひどく重く、最適化できない。

例外

有理数クラスでは、分母がゼロとなることは決してない。 （本ライブラリでは、NaN や無限大の表現形式としても、分母がゼロになることはない） そのため、分母の値が０となる場合には、boost::bad_rational 例外（これは、std::domain_error のサブクラスである）をスルーする。 これは、ユーザーが分母を０としてコンストラクタを実行した場合と、任意の有理数クラス数値を、ゼロで除算しようとした際にのみ発生する。

さらに、基本要素となる整数型での演算の結果、例外が発生した場合には、その例外は有理数クラスクラスに伝番する。 原則はひとつである。基本要素となる整数型がスルーするあらゆる例外は、有理数クラスのあらゆる演算に於いてスルーされる。 加えて、有理数クラスのコンストラクタは、正規化の段階に於いて基本要素クラスで発生した例外をスルーする。 この事項に対する唯一の例外事項は、有理数クラスのデストラクタは、基本要素クラスのデストラクタがスルーした例外しかスルーしないということである（ただし、通常デストラクタの実行中に基本要素クラスで例外が発生することはない）

内部表現

補足： ここで記述する内容は単純に情報を提供するためにのものにすぎない。 プログラミングの際に、ここで述べるような実装の詳細に依存するようなプログラムを書くべきではない。

内部的には有理数クラスは、分子・分母の２つの整数型（テンプレートで与えられる型パラメータである）の値として保持される。 有理数クラスの内部表現に置いては、常に約分（すなわち、分子と分母の最大公約数が１となる状態）され、分母が正であるように正規化されている。

デザインノート

最小の構成となるような設計

有理数クラスは数としての基本原則を崩さないように実装されている。 有理数として持つべき最小限の機能しか持たないが、基本要素となる整数型にアクセスするための、 numerator() と denominator() の関数を持つことで、必要に応じて、どのような機能拡張も行うことができる。

入出力と、 rational_cast() の関数については厳密には、有理数として持つべき最小構成の範囲からは逸脱している。 入出力については明らかであろう。 しかしながら、浮動小数点型の変数に型変換するたために、 rational_cast() が最善でない場合もある。 （ことにユーザー定義型の浮動小数点型への変換は複雑である） こういった場合には、ユーザー定義の型変換関数を定義することができるし、また、すべきである。 このユーザー定義による型変換関数が、 rational_cast() という名前である必要はない。 そのため、 rational_cast() が、特殊化／オーバーロード可能な形で定義される 必要はない 。

基本要素の数値表現範囲（Limited-range integer types）

有理数クラスは、表現範囲に制限のないような整数型を使用するように設計されている。 このような整数型を要素として利用する場合には、演算結果は常に正確に表現され、桁落ちやオーバーフロー／アンダーフローの問題も発生することはない。

不幸なことに、標準の C++ においては、このような整数型を使用することはできない（boost ライブラリにおいても、現時点では同様である） このような事情で、有理数クラスは、多分、C++ の int のような、数値表現の範囲に限界を持った型を基本要素として使用されるであろう。

数値表現の範囲が限定されるような要素を基本要素として使用した場合、有理数クラスは、ちょうど浮動小数点型と同じような多くの精度の問題に見舞われる。 しかしながら、有理数クラスがシンプルな使われ方をしている限りは精度の問題が表面化することは少ないものと考える。 それでも、ユーザーは整数型の表現範囲が制限されることによる精度の問題が発生しうることを考慮しておくべきである。

表現範囲が制限された整数型の影響による問題点を、C++ の int を 32bit の符号付きであるものとして説明する。 この場合、 rational<int> として表現できるもっとも小さな正数値は、1/0x7FFFFFFF である。 換言すれば、０の近辺では、 rational<int> で表現できる“粒度”は、約 4.66e-10 である。 他方、 rational<int> で表現可能な最大の数は、0x7FFFFFFF/1 であり、 rational<int> におけるその次に小さい数は、0x7FFFFFFE/1 である。 これは、表現可能な最大値付近では数値の粒度は１であることを意味している。 このように、数値の粒度が数値の絶対値の影響を受けることがすなわち、浮動小数点数と同じ特徴なのである。 しかしながら、このような性質は有理数クラスを使用する上で、自然なものとは“感じられない”だろう。

有理数クラスの基本要素として、表現範囲が制限された整数型を使用することの得失に注意し、前もって意識するのはユーザー次第だということである。

浮動小数点型からの型変換

有理数クラスライブラリでは、浮動小数点型から有理数クラスへの型変換関数を提供していない。 浮動小数点型から有理数クラスへの型変換関数を希望する意見をいくつか受け取ってはいる。 しかしながら、boost における広範な議論の結果として、浮動小数点型からの型変換には“最適解”が存在しないという結論に達した。 本ライブラリのユーザーが、その目的に適した型変換関数を作成することは可能であるが、そのいずれをも、“スタンダード”として採用することはできなかった。

浮動小数点型からの型変換を行う際にもっとも大きな問題となるのは、浮動小数点型の演算における誤差をどう扱うかという点である。 以下のコードで具体的な例を示す

// 以下の２つの数値は、ユーザによる入力であったり、
// 計測器からの入力であったりする。
double x = 1.0;
double y = 3.0;

double z = x/y;

rational<I> r = rational_from_double(z);

根本的な疑問は、この場合 r の値はどうなるかということである。 自然な回答は、1/3 ということになるが、これはたくさんの問題を無視しているものである。

まず、z は厳密には 1/3 でないという点が挙げられる。 浮動小数点型の持つ制度上の限界から、どのような表現形式を以てしても 1/3 を厳密に表現することはできないのである。 それなら、r は、z それ自体の値を（厳密に）に表現すればよいのだろうか？ r の値として、33333333333333331/100000000000000000 を用いることが適切なのであろうか？

しかし、z の厳密性を議論する前に、そもそも、x と y の厳密性について議論しなければならない。 例えば、x や y の値がアナログ的な計測器の計測結果であったとしたら、常に有限の精度でしか評価できない。 この場合、有理数クラスで勝手な桁数の精度を一律に仮定することは、元の精度を悪化させることになる。

このような議論ののち、“単純な整数比のうちで、最も近いもの”を探すべきなのではないかと思うかもしれない。 しかも、このような数値を求めるためのアルゴリズムは実際に存在する。 しかしながら、すべてのアプリケーションでこの方法が最適であるとは限らない。 別の例では、一連の計算における桁落ちを防止するために、有理数クラスへの変換の際に正確性が要求される。 この場合には、たとえ数値表現の上で“不自然”であったとしても、厳密な値を表現する必要がある。

このような相容れない要求に対して、万人を満足させる単一の解決方法を見いだすことはできなかった。 その上に、有理数クラスの演算に対するアルゴリズムは複雑であり、また専門化されているため、アプリケーションに要求される事項を理解した上で、最適な実装を行うことが良いと考える。

絶対値

普通に考えれば、基本要素となる整数型の絶対値 abs(IntType) が定義されていれば、これを用いて、有理数クラスにおける絶対値（ rational<IntType> ）が定義されているべきであると考えられるだろう。 しかしながら、絶対値を定義するにはいくつもの問題が存在する。

最初の問題は、 abs() 関数の探索に関する問題である。 asb(IntType) の実装を調べるためには、特に、IntType がユーザーの定義した形であり、ユーザー定義の名前空間にある場合、Koenig lookup （関数を引数の所属する名前空間で探索すること）が必須となる。 現時点では、関数についてはこの機能をサポートしていないコンパイラも存在する。 このような機能をサポートしないコンパイラを使用する場合には、ユーザーは意図的に、有理数クラスの動作と協調できるようなクラス設計を行う必要がある。

次の問題は、標準的でない組込整数型の問題であり、こちらの方がより深刻な問題であると考えられる。 long long や __int64 のような標準的でない組み込み整数型に対して、コンパイラベンダーが abs() 関数を提供するという保証がないことである。 これは、実装品質の問題ではあるが、しかしながら、long long のような型の追加自体が多分に場当たり的なものであるのだ。

結論は、 abs(IntType) を使用して、 abs(rational<IntType>) を定義することは実用的ではないということだ。 代わりに、以下のシンプルなインライン関数を使用している。

template <typename IntType>
inline rational<IntType> abs(const rational<IntType>& r)
{
    if (r.numerator() >= IntType(0))
        return r;

        return rational<IntType>(-r.numerator(), r.denominator());
}

このことから、基本要素となる整数型の絶対値が他の場所で定義されたとしても、有理数クラスの絶対値はインライン関数で計算できるということがわかる。

リファレンス

• 有理数クラスのヘッダファイル： rational.hpp
• サンプルコード： rational_example.cpp
• 回帰テスト： rational_test.cpp

History and Acknowledgements

1999年12月著者（原著者 Paul Moore）は、有理数クラスの最初の実装を行い、 boost.org メーリングリストに投稿した。 メーリングリストにおいて、いくつかの議論が交わされた。 殊に、Andrew D. Jewell は、オーバーフローとアンダーフローの発生を防止することの重要性を指摘するとともに、ほとんどの基本的な数値演算に於いてオーバーフローを回避するための実装方法を提供してくれた。 rational_cast は、Kevlin Henney の提案によるものである。 Ed Brey は、オリジナルのソースコードにあった、少なくないタイプミスについて、重要なコメントを与えてくれた。

David Abrahams は、このドキュメントに於いて有用なフィードバックを行ってくれた

浮動小数点型から、有理数クラスへの型変換関数を提供することについては、boost メーリングリストで、2000年11月に長い議論が交わされた。 Reggie Seagraves, Lutz Kettner そして、Daniel Frey を含む、メンバーがこの点の中心メンバーとなった（もっとも、boost メーリングリストのほとんどのメンバーがそれぞれに、白熱した議論に参加していたのを感じているが）それでもなお、議論の最終結論としての実装は 行えなかった。 浮動小数点からの変換関数を巡る問題を理解するためには、このメーリングリストでの議論は価値のあるものである。

Stephen Silver は、有理数クラスをユーザー定義の整数型の上で使用する際の、有用な知見を示してくれた。

Nickolay Mladenov は、operator+= と operator-= の、現行の実装を提供してくれた。

上述した、有理数クラスの理論的な説明部分、絶対値 と、Swap Operation に現れた、Koenig lookup と、std::swap について議論は、2001年1月に、boost メーリングリストで行われた。

Revised February 5, 2001

(c) Copyright Paul Moore 1999-2001. Permission to copy, use, modify, sell and distribute this document is granted provided this copyright notice appears in all copies. This document is provided "as is" without express or implied warranty, and with no claim as to its suitability for any purpose.

Japanese Translation Copyright (C) 2003 FUJIHARA Keiichi keiichi@fujihara.name. オリジナルの、及びこの著作権表示が全ての複製の中に現れる限り、この文書の複製、利用、変更、販売そして配布を認める。 このドキュメントは「あるがまま」に提供されており、いかなる明示的、暗黙的保証も行わない。 また、いかなる目的に対しても、その利用が適していることを関知しない。