任意精度算術ライブラリGMP
今までGCCをコンパイルするとき何となしにビルドしていたGMP。
このライブラリ、なんなのかようやく知る機会を得た。
（そもそもビルドするときに何なのか疑問をもつべきではあったが）
そもそもこのライブラリ、
GNU Multiple Precision Arithmetic library
というらしい。つまり任意精度算術ライブラリだ。
数値の精度
知る人にとっては当然のことだが、普段プログラミング言語で扱う数値には精度の限界がある。
たとえば、いちばんわかりやすい例で言うとC言語のint型は32bitであるため、2^32通りの数値しか表せない。
int型は正数と負数の両方を表せるため、-2^31〜(2^31)-1の値を取り得る。
-2147483648〜2147483647のようだ。
つまり、10桁程度までしか扱うことができない。
これをunsigned intに変えたところで、2倍程度の数値までしか扱えない。
勿論、longとかlong longに変えても限度はあるので、根本的解決にはならない。
これが数値の精度の限界だ。
ちなみに、浮動点小数の精度問題も興味深い話題ではあるが、今回は話を簡潔に進めるために割愛する。
GMPを見てみる
まずはサンプルコードを見てみる。
今回は本質的な部分以外を抽象化するため、C言語ではなくC++で書いた。
#include <iostream> #include <string> #include <gmpxx.h> using namespace std; enum { BASE = 10 }; mpz_class factorial(mpz_class n) { if(n == 0) { return 1; } else { return n * factoriall(n-1); } } int main() { mpz_class a; string buf; cout << "n! >> "; while(cin >> buf) { a.set_str(buf, BASE); cout << factorial(a).get_str() << endl; cout << "n! >> "; } }
GMPを使っているので、コンパイルは以下のようにフラグをつける。
$ g++ -lgmp -lgmpxx -o test test.cpp
GMPを用いることで上記の問題を解決できるわけだ。
このプログラムは階乗を求めるプログラムだ。
しかしご存知の通り、階乗はnの値が少し大きくなっただけでとんでもなく大きくなる。
0!=1
1!=1
2!=2
3!=6
4!=24
5!=120
6!=720
7!=5040
8!=40320
9!=362880
10!=3628800
とたった10!でも7桁になってしまう。
従来のint型では確か16!かそこらくらいまでしか計算できなかったはずだ。
しかし、このプログラムのようにmpz_classというクラスを用いれば大きな桁でも扱えるようになる。
試しに1000!を計算してみると…
とのことらしい。
スクショだけではわからないが、実はこれ、ほぼ一瞬で計算できる。
コードの解説
C++用のgmpxxなら話は簡単だ。
mpz_classというクラスのインスタンスを作成するだけで、あとは
- mpz_class::set_str(const char *number, int base)で初期化（baseは基数）
- mpz_class::get_str()で文字列を取得
たったこれだけである。
なぜこれほどにまで簡単に扱えるのかというと、話は単純で、泥臭い部分を演算子オーバーロードしてあるからだ。
だから、あとは単純にa+bとかa*bとか好きなようにしてやればいい。
詳しくはこちらの公式ドキュメントを参照してほしい。
【参考】GNU MP - C++ Class Interface
