読者です 読者をやめる 読者になる 読者になる

任意精度算術ライブラリ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!を計算してみると…

f:id:levelfour:20140118225742p:plain

とのことらしい。
スクショだけではわからないが、実はこれ、ほぼ一瞬で計算できる。

コードの解説

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

最後に

実はC言語でGMPを扱うと、mpz_tという型に対してmpz_initとかmpz_clearとか呼んで…とかクソ面倒くさい。
ていうか、これどう見ても内部ポインタ持ってるな。
と思ってデバッグしかけたけど、デバッグスキルが貧弱すぎて全然わからなかった。
中に_mp_alloc、_mp_size、_mp_dというプロパティがあるらしいことまではわかったけど、どうもメモリをダンプしてもゴミデータしか出てこない。
そろそろGDBを真面目に勉強するときなのだろうか。

ちなみに

GMPはGNUの遺産なのでLGPLライセンスになっている。
そのため、ソースコードの公開が必須となり、商用等に使えない問題が出てくる。
この辺に困っているのがHaskellのようで、Haskellは従来integer-gmpという方式で整数型を扱ってきたのだが、最近はinteger-simpleというHaskell自身による任意精度整数の実装が普及しつつあるらしい。
僕はHaskellを触り始めたばかりでこれ以上のことは何も知らないので、詳しくはHaskellerに聞いてほしい。