C++で多倍長整数ライブラリGMPを使う
目的
GCJなど一部のプログラミングコンテストでは既存のライブラリを使用することが認められている。
特にC++であれば多倍長整数ライブラリとしてGMPを使うのが妥当であると考えられる。GMPを直接叩くのもよいが、GMPのC++バインディングを使うのが簡単であると考えた。
GMPのインストール
Cygwinの場合は、インストーラーから libgmp-devel とその依存関係をインストールすればよい。
Ubuntuの場合は、aptでlibgmp-devをインストールすればよい。
他の場合は未調査。
コンパイル
例えば、次のようにしてコンパイルする。(他のオプションは適宜補う)
g++ main.cpp -lgmpxx -lgmp
このとき、引数の順番に注意すること。
例えば、ライブラリ指定をコンパイル対象より前に置いてしまうと、次のようなエラーメッセージが出る。(ライブラリ指定を忘れた場合も同様)
/tmp/cco0O7Yl.o: In function `__gmp_binary_plus::eval(__mpz_struct*, __mpz_struct const*, __mpz_struct const*)': main.cpp:(.text._ZN17__gmp_binary_plus4evalEP12__mpz_structPKS0_S3_[_ZN17__gmp_binary_plus4evalEP12__mpz_structPKS0_S3_]+0x27): undefined reference to `__gmpz_add' /tmp/cco0O7Yl.o: In function `__gmp_binary_multiplies::eval(__mpz_struct*, __mpz_struct const*, __mpz_struct const*)': main.cpp:(.text._ZN23__gmp_binary_multiplies4evalEP12__mpz_structPKS0_S3_[_ZN23__gmp_binary_multiplies4evalEP12__mpz_structPKS0_S3_]+0x27): undefined reference to `__gmpz_mul' /tmp/cco0O7Yl.o: In function `__gmp_binary_multiplies::eval(__mpz_struct*, __mpz_struct const*, long)': main.cpp:(.text._ZN23__gmp_binary_multiplies4evalEP12__mpz_structPKS0_l[_ZN23__gmp_binary_multiplies4evalEP12__mpz_structPKS0_l]+0x27): undefined reference to `__gmpz_mul_si' /tmp/cco0O7Yl.o: In function `__gmp_expr<__mpz_struct [1], __mpz_struct [1]>::__gmp_expr()': main.cpp:(.text._ZN10__gmp_exprIA1_12__mpz_structS1_EC2Ev[_ZN10__gmp_exprIA1_12__mpz_structS1_EC5Ev]+0x14): undefined reference to `__gmpz_init' /tmp/cco0O7Yl.o: In function `__gmp_expr<__mpz_struct [1], __mpz_struct [1]>::__gmp_expr(int)': main.cpp:(.text._ZN10__gmp_exprIA1_12__mpz_structS1_EC2Ei[_ZN10__gmp_exprIA1_12__mpz_structS1_EC5Ei]+0x20): undefined reference to `__gmpz_init_set_si' /tmp/cco0O7Yl.o: In function `__gmp_expr<__mpz_struct [1], __mpz_struct [1]>::~__gmp_expr()': main.cpp:(.text._ZN10__gmp_exprIA1_12__mpz_structS1_ED2Ev[_ZN10__gmp_exprIA1_12__mpz_structS1_ED5Ev]+0x14): undefined reference to `__gmpz_clear' /tmp/cco0O7Yl.o: In function `std::ostream& operator<< <__mpz_struct [1], __mpz_struct [1]>(std::ostream&, __gmp_expr<__mpz_struct [1], __mpz_struct [1]> const&)': main.cpp:(.text._ZlsIA1_12__mpz_structS1_ERSoS2_RK10__gmp_exprIT_T0_E[_ZlsIA1_12__mpz_structS1_ERSoS2_RK10__gmp_exprIT_T0_E]+0x32): undefined reference to `operator<<(std::ostream&, __mpz_struct const*)' /tmp/cco0O7Yl.o: In function `__gmp_expr<__mpz_struct [1], __mpz_struct [1]>::__gmp_expr<__gmp_binary_expr<__gmp_expr<__mpz_struct [1], __mpz_struct [1]>, __gmp_expr<__mpz_struct [1], __mpz_struct [1]>, __gmp_binary_plus> >(__gmp_expr<__mpz_struct [1], __gmp_binary_expr<__gmp_expr<__mpz_struct [1], __mpz_struct [1]>, __gmp_expr<__mpz_struct [1], __mpz_struct [1]>, __gmp_binary_plus> > const&)': main.cpp:(.text._ZN10__gmp_exprIA1_12__mpz_structS1_EC2I17__gmp_binary_exprIS2_S2_17__gmp_binary_plusEEERKS_IS1_T_E[_ZN10__gmp_exprIA1_12__mpz_structS1_EC5I17__gmp_binary_exprIS2_S2_17__gmp_binary_plusEEERKS_IS1_T_E]+0x18): undefined reference to `__gmpz_init' /tmp/cco0O7Yl.o: In function `__gmp_expr<__mpz_struct [1], __mpz_struct [1]>::__gmp_expr<__gmp_binary_expr<__gmp_expr<__mpz_struct [1], __mpz_struct [1]>, __gmp_expr<__mpz_struct [1], __mpz_struct [1]>, __gmp_binary_multiplies> >(__gmp_expr<__mpz_struct [1], __gmp_binary_expr<__gmp_expr<__mpz_struct [1], __mpz_struct [1]>, __gmp_expr<__mpz_struct [1], __mpz_struct [1]>, __gmp_binary_multiplies> > const&)': main.cpp:(.text._ZN10__gmp_exprIA1_12__mpz_structS1_EC2I17__gmp_binary_exprIS2_S2_23__gmp_binary_multipliesEEERKS_IS1_T_E[_ZN10__gmp_exprIA1_12__mpz_structS1_EC5I17__gmp_binary_exprIS2_S2_23__gmp_binary_multipliesEEERKS_IS1_T_E]+0x18): undefined reference to `__gmpz_init' /tmp/cco0O7Yl.o: In function `__gmp_expr<__mpz_struct [1], __mpz_struct [1]>::__gmp_expr<__gmp_binary_expr<__gmp_expr<__mpz_struct [1], __gmp_binary_expr<long, __gmp_expr<__mpz_struct [1], __mpz_struct [1]>, __gmp_binary_multiplies> >, __gmp_expr<__mpz_struct [1], __mpz_struct [1]>, __gmp_binary_plus> >(__gmp_expr<__mpz_struct [1], __gmp_binary_expr<__gmp_expr<__mpz_struct [1], __gmp_binary_expr<long, __gmp_expr<__mpz_struct [1], __mpz_struct [1]>, __gmp_binary_multiplies> >, __gmp_expr<__mpz_struct [1], __mpz_struct [1]>, __gmp_binary_plus> > const&)': main.cpp:(.text._ZN10__gmp_exprIA1_12__mpz_structS1_EC2I17__gmp_binary_exprIS_IS1_S4_IlS2_23__gmp_binary_multipliesEES2_17__gmp_binary_plusEEERKS_IS1_T_E[_ZN10__gmp_exprIA1_12__mpz_structS1_EC5I17__gmp_binary_exprIS_IS1_S4_IlS2_23__gmp_binary_multipliesEES2_17__gmp_binary_plusEEERKS_IS1_T_E]+0x18): undefined reference to `__gmpz_init' /tmp/cco0O7Yl.o: In function `__gmp_expr<__mpz_struct [1], __mpz_struct [1]>::__gmp_expr<__gmp_binary_expr<long, __gmp_expr<__mpz_struct [1], __mpz_struct [1]>, __gmp_binary_multiplies> >(__gmp_expr<__mpz_struct [1], __gmp_binary_expr<long, __gmp_expr<__mpz_struct [1], __mpz_struct [1]>, __gmp_binary_multiplies> > const&)': main.cpp:(.text._ZN10__gmp_exprIA1_12__mpz_structS1_EC2I17__gmp_binary_exprIlS2_23__gmp_binary_multipliesEEERKS_IS1_T_E[_ZN10__gmp_exprIA1_12__mpz_structS1_EC5I17__gmp_binary_exprIlS2_23__gmp_binary_multipliesEEERKS_IS1_T_E]+0x18): undefined reference to `__gmpz_init' collect2: error: ld returned 1 exit status
サンプル
整数nとmを入力すると、フィボナッチ数列のn番目を計算するプログラム。
- m = 1 のとき、再帰による計算を行う。(四則演算の回数は指数オーダー)
- m = 2 のとき、動的計画法による計算を行う。(四則演算の回数は線形)
- m = 3 のとき、行列累乗による計算を行う。(四則演算の回数は対数オーダー)
#include <iostream>
#include <gmpxx.h>
mpz_class fib1(int), fib2(int), fib3(int);
int main() {
int n, m;
std::cin >> n >> m;
if(m == 1) {
std::cout << fib1(n) << std::endl;
} else if(m == 2) {
std::cout << fib2(n) << std::endl;
} else if(m == 3) {
std::cout << fib3(n) << std::endl;
}
return 0;
}
mpz_class fib1(int n) {
if(n <= 1) return n;
else return fib1(n - 1) + fib1(n - 2);
}
mpz_class fib2(int n) {
mpz_class a = 1, b = 0;
for(int i = 0; i < n; ++i) {
swap(a, b);
b += a;
}
return b;
}
mpz_class fib3(int n) {
mpz_class a = 1, b = 0, c, d;
for(int i = 30; i >= 0; --i) {
c = a * a + b * b;
d = b * (2 * a + b);
if((n >> i) & 1) {
b = c + d;
swap(a, d);
} else {
swap(a, c);
swap(b, d);
}
}
return b;
}
解説
mpz_classは、GMPの多倍長整数のC++によるラッパークラスである。これはintとほぼ同じように取り扱うことができる。
- 四則演算はほぼ通常通り使える。
- iostreamを用いる場合は、intと同様に読み書きできる。
- intからの自動キャストがある。
mpz_classは通常の整数型とは違い、生成コストやコピーコストに気を使ったほうがよい場面がある。vectorと同様、mpz_classには高速なswapが定義されているので、それを用いるのがよい(気がする)。
最近のGMPのC++バインディングにはムーブコンストラクタが定義されている。C++11を使うとコピーコストが低くなる場面があるかもしれない。(未検証)
