English | 日本語
最終更新: 2016/12/30

kv - C++による精度保証付き数値計算ライブラリ

柏木 雅英

1. はじめに

本ページでは、精度保証付き数値計算を行うためにC++で作成した ライブラリ群を公開している。

特に非線形計算の精度保証を行うとき、template機能によって 複雑な数値型をすっきり記述でき、なおかつ "zero-overhead principle" で 計算速度が遅くならないC++は、非常に適していると言える (ほぼ唯一無二であると作者は考えている。)。

2007年秋頃~2013年春頃の間は、区間演算を行うのにboostに含まれている intervalライブラリを用いて開発していたが、 boost.intervalは残念ながら不完全な部分が多く ライブラリ本体に手を入れざるを得なかった。 boost全体がアップデートする度にinterval部分にpatchを当てるのも面倒になって きたので、interval部分は全て自作することにした。 本ライブラリはboost.intervalは使っていないが、線形計算を行うboost.ublasなど、 部分的にまだboostを使っている。

boost.intervalを使っていた頃の古い情報はもうアップデートしないが、 一応 ここに保存しておく。

2. 動作環境

C++とboostが動くことが必要。boostが動かないといけないので、あまり古い コンパイラでは動作しないだろう。

区間演算を実現するために丸めモードの変更を行っているので、 CPUとコンパイラには制限がある。 詳細は 区間演算(interval) の項を参照。

また、 4倍精度演算 を行うときにIntelのFPUは いろいろ問題を抱えており、一応対策しているが、特に32bitモードでは問題が 発生する可能性があることを注意しておく。

一応、次の環境で動作を確認したことがあるが、主に開発は ubuntu 14.04 64bitで行っており、その他は コンパイルが通るかチェックする程度である。

3. ダウンロードとインストール

ダウンロード: kv-0.4.39.tar.gz (2016年12月30日公開)
(古いversionはこちら)

ヘッダファイルのみで動くように作られている。よって、ライブラリをmakeする 等のインストール作業は必要ない。 archiveを展開するとkv, test, exampleの3つのdirectoryが作られるが、 本体は kv 以下。kv以下をどこか (current directoryでも/usr/local/includeでも) に置いておくだけで良い。 動作確認は、kv及びboostがinclude pathに入った状態でtest以下または example以下の適当な.ccファイルをコンパイル出来ればOK。 例えば、

ならば、例えばtest以下で
c++ -I.. -I/usr/local/include test-interval.cc
とやってエラーが出なければ問題ない。 (「kv及びboost directoryが置いてあるdirectory」を指定することに注意)

コンパイルオプションは、-O3等で最適化を最大にし、 -DNDEBUGを付けることを推奨。 どちらも実行速度に大きく影響する。 (NDEBUGマクロの意味は boost.ublasの項を参照。) また、IntelのCPUで64bit OSの場合は、-DKV_FASTROUND を付けると区間演算が速くなる。

([2015/12/17]に追加) 新しい環境やコンパイルオプションを使うときは、test/test-rounding.ccをコンパイル/実行して、 加減乗除と平方根で丸めの向きがちゃんと変わっているか簡易チェックするとよい。

kvライブラリが提供する機能は全てkv名前空間の中にあり、他のライブラリと ぶつからないように配慮されている。

4. 構成ファイルの役割一覧

5. 区間演算(interval)

6. 4倍精度演算(dd)

7. MPFRラッパー

8. 複素数演算(complex)

9. 自動微分(autodif)

10. Affine Arithmetic (affine)

11. ベキ級数演算 (psa)

12. Krawczyk法による非線形方程式の解の精度保証

13. 非線形方程式の全解探索

14. 常微分方程式の初期値問題の精度保証

15. 初期値問題solverと射撃法による境界値問題の精度保証

16. 数値積分

17. 特殊関数の精度保証

18. その他の機能

19. 関数オブジェクトによる問題の記述

20. その他

20.1 boostとは

20.2 行列計算 (boost.ublas)

20.3 数値型のプログラミング

20.4 おまけ: シンプルな区間演算ライブラリ

21. kvライブラリのwebデモ

kvライブラリをweb上で試せるデモ。

22. おわりに

本ライブラリは、 HIKMOT のC++パートで使われ、その高速性に大きく寄与しています。 また、当研究室の学生の日々の研究にも使われ、 その意見を反映しながら開発を進めています。

大勢の人に使われて鍛えられないとライブラリは成長しないので、 なるべく多くの方に使って頂いてご意見を頂ければありがたいです。

本ライブラリの開発には、NTT未来ねっと研究所の柏木啓一郎氏の多大なる協力を 得ています。ここに感謝の意を表します。

(2015年10月5日追記) このソフトウェアはMITライセンスに基づいて公開されています。

更新履歴

開発にご協力下さった方々


kv - a C++ Library for Verified Numerical Computation /