C++ の Boost 区間演算ライブラリの使い方などのまとめです。内容は基本的に Boost Interval Arithmetic Library - Boost 1.49.0 からの抜粋要約(兼自分用メモ)です。
# 私も完璧には理解していないですし、何より本家のドキュメント自体が不完全で、全訳してる訳でもないので、あまり本稿の内容を信用しないでください。書いてあることが違っていても私は責任取れません。
## 全体で結構な量になりそうなので、何回かに分割してやっていきたいと思います。今回は区間演算のコンセプトについてのお話が主なので、使い方とか技術的な事を期待している方は次回以降にご期待ください。
概要: 区間演算ライブラリとは
区間演算ライブラリとは、文字通り数学の「区間」を扱うためのライブラリです。Boost の区間演算ライブラリは、#include <boost/numeric/interval.hpp>
するだけで簡単に使えます。実際に見た方が早いでしょう:
# include <iostream>
# include <boost/numeric/interval.hpp>
# include <boost/numeric/interval/io.hpp>
int main () {
boost::numeric::interval<int> a(-1, 2);
std::cout << a << std::endl;
return 0;
}
$ g++ hello-interval.cpp -o hello-interval
$ ./hello-interval
[-1,2]
このように、区間のベースとなる型 T をテンプレート引数にとる区間型 boost::numeric::interval<T>
が使えるようになります。実は、この区間型は interval<T, Policies>
と 2 つのテンプレート引数をとるように宣言されていて、Policies に色々指定することで細かい挙動を変えることもできます。省略時はデフォルトポリシーが使われて、普通はデフォルトのもので十分なので今回はポリシーについては詳しくはやりません(後でまたまとめる予定)。
Remark. 区間演算ライブラリは、どんな計算機・どんなコンパイラに対しても「正確な計算」をサポートしている訳ではありません(ここで言う「正確な計算」の意味は後述します)。使っている計算機環境で区間演算ライブラリが正しく使えるかどうかは後半に載せているサンプルや本家ドキュメントなどで各自確認してください。
区間演算のコンセプト
区間演算の話をする前に、まず「区間」というものについて確認しておくと、ここでの 区間 とは、「2 つの数の間にある 全ての 数を表現するもの」のことです(数学用語で言う所の閉区間ですね)。「全ての」という所がポイントです。また、区間は [a, b] と書くことにしましょう。
さて区間演算について説明しましょう。 区間演算 とは、「(通常の数の)演算結果を 全て 包含するような区間を計算するもの」です。ここで大事になるのが区間同士の包含関係です。
通常の数を引数に取る関数(演算)f を考えます。関数 f は、自然に区間 [a, b] を引数にとるような関数に拡張できます。つまり f([a, b]) を、任意の a≦x≦b に対して f(x) を含むような最小の区間として定義することができます。このように、「全ての x∈[a, b] に対し f(x)∈f([a, b])」という性質のことを、 包含単調性 と呼びます(二項演算など、引数の数が変わっても同様です)。
この包含単調性の考え方が、 浮動小数点数の区間演算 において非常に大事になります。例えば、double 型の加法演算 + を interval 上に拡張することを考えてみます。2 つの区間 [a, b] と [c, d] を足した結果は何でしょうか?足した結果を__全て__包含するような区間にしたいので、[a, b] + [c, d] は [a + c, b + d] と定義するのが良さそうです。でもちょっと待ってください。結果の区間は__本当に全ての__演算結果を含んでいますか?
ここが浮動小数点演算の落とし穴ですね。そうです、__誤差__です。double として a + c を計算して丸めてしまうと、数学的に厳密な値としての a + c が計算機的な区間としての [a + c, b + d] に含まれているかどうか一般には分かりません。
そこで、丸め誤算のことまで考えて、[a, b] + [c, d] の定義として [down(a + c), up(b + d)] を採用することにします(ここで down, up は IEEE 標準で定められている浮動小数点演算の切り捨て・切り上げを表します)。こうすれば、区間演算 + は包含単調性をもちます。
# 勘の鋭い方はもう気付いたと思いますが、まぁ実際には話の流れが逆な訳ですね。元々、浮動小数点演算がどうしても生んでしまう誤差を定量的に見積もるための手法として包含単調性を持つ区間演算というコンセプトが考え出された訳です[要出典]。包含単調性を持つ区間演算で計算している限りは、真の計算値が(それが実際に何であるかや実際の誤差までは分からないにせよ)どの程度の範囲(区間)にあるかを定量的に見積もることができます。
区間演算と単調包含性の例
では実際に加法の演算が単調包含性を持っているかどうか確認してみましょう。
# include <iostream>
# include <boost/numeric/interval.hpp>
# include <boost/numeric/interval/io.hpp>
int main () {
using namespace std;
using namespace boost::numeric;
typedef double R;
typedef interval<R> IR;
const R eps(1.0e-14);
const IR one(1.0);
const IR x = one + eps - one;
cout << "eps = " << eps << endl;
cout << "one = " << one << endl;
cout << "x = one + eps - one = " << x << endl;
cout << "width(x) = " << width(x) << endl;
cout << "eps is " << (in(eps, x) ? "" : "not ") << "in x" << endl;
return 0;
}
x86 / g++ ではこのような結果になりました:
$ g++ test-interval-double.cpp -o test-interval-double
$ ./test-interval-double
eps = 1e-14
one = [1,1]
x = one + eps - one = [9.99201e-15,1.02141e-14]
width(x) = 2.22045e-16
eps is in x
一方、clang++ など他のコンパイラを使ったり、プロセッサの種類によっては、異なる結果になるかもしれません:
$ clang++ test-interval-double.cpp -o test-interval-double
$ ./test-interval-double
eps = 1e-14
one = [1,1]
x = one + eps - one = [9.99201e-15,9.99201e-15]
width(x) = 0
eps is not in x
このように、「正確な計算」が行われるかどうかは、計算機とコンパイラの環境にかなり依存しています(もちろん、ここで言う「正確な計算」というのは、真の計算値を含むよう 包含単調性 を保ちつつ計算が行われていることを指します)。なので、これから区間演算を試そうという方はこの点によく留意しておいてください。
# 余談。このサンプルプログラムを書く際、Vim QuickRun プラグインを使って逐一実行結果の確認しながら書いていたのですが、最初なぜか思ったように包含単調性が確認できませんでした。試行錯誤の末に諦めて vim を一旦閉じ、時間をおいてから自分で g++ でコンパイルしてみたらちゃんと期待通りの動きをして、びっくりしました。原因を調べてみたら quickrun.vim で clang++ の方が優先して使われる設定だった、というオチ。いやぁ、まさか同じマシンで同じプログラムをコンパイルできて実行もできているのにコンパイラによって結果が違うとは… 怖いですね。
今日はここまで。明日は他の区間演算や組み込み関数などに触れたいと思います。ではでは。
今回のサンプルプログラムと入出力例: https://gist.github.com/2937001
次: boost::numeric::interval<int>(1): C++ Boost 区間演算ライブラリ 四則演算と基本的な関数