c言語でGMPを使って多倍長演算
c言語で標準では多倍長整数がサポートされていないのでこれらを扱いたい場合は自分で実装するかライブラリーを使う必要があります。
そこで今回はGMP(GNU Multi-Precision Library)という算術ライブラリを利用して多倍長整数を使ってみたいと思います。
https://gmplib.org/manual/index.html
片っ端からやっていってもきりがないので必要そうなところを触れておきたいと思います。
コンパイル
コンパイルは以下のように行います。
1 |
gcc gmp_sample.c -o gmp_sample -lgmp |
変数の初期化
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
#include <gmp.h> int main() { mpz_t a,b,c; // 初期化 mpz_init(a); mpz_set_ui(a,1234567890); // 初期化してわりあて mpz_init_set_ui(b,9876543210); mpz_init_set_ui(c,1234987654321); gmp_printf ("mpz_init_set_ui %Zd\n", a); gmp_printf ("mpz_init_set_ui %Zd\n", b); gmp_printf ("mpz_init_set_ui %Zd\n", c); // mpz_tをmpz_tへコピー mpz_set(b,a); gmp_printf ("mpz_set %Zd\n", b); // 文字列から数値を生成 mpz_set_str(a,"12394872039846520983745092837458238947528346283745802837468238947520137489572463589",10); mpz_set_str(b,"39846520983745092837458238947528346283745802837468238947520137489572463589",10); mpz_set_str(c,"12394872039846520983745092837458238947528346283745802837468238947520137489572463589",10); gmp_printf ("mpz_set_str %Zd\n", a); gmp_printf ("mpz_set_str %Zd\n", b); gmp_printf ("mpz_set_str %Zd\n", c); return 0; } |
ソースを見ればなんとなく何をやっているかわかるかと思います。
gmpではmpz_tという型を主に使うようですが、
mpz_tは値を割りあてたり演算をする前に初期化しなければいけないようです。
mpz_initで変数を初期化できます。
mpz_init_set_uiで初期化と割り当てを同時にすることもできます。
uiというのはunsigned intのことです。
int型だけでなくmpz_set_dでdouble型も割り当てることができます。
演算
加算
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
#include <gmp.h> int main() { mpz_t a,b,c; mpz_init(a); mpz_set_str(a,"12394872039846520983745092837458238947528346283745802837468238947520137489572463589",10); mpz_init_set_str(b,"39846520983745092837458238947528346283745802837468238947520137489572463589",10); mpz_init_set_str(c,"12394872039846520983745092837458238947528346283745802837468238947520137489572463589",10); gmp_printf ("mpz_set_str %Zd\n", a); gmp_printf ("mpz_set_str %Zd\n", b); gmp_printf ("mpz_set_str %Zd\n", c); mpz_add(c, a, b); gmp_printf ("mpz_add %Zd\n", c); return 0; } |
1 2 3 4 |
mpz_set_str 12394872039846520983745092837458238947528346283745802837468238947520137489572463589 mpz_set_str 39846520983745092837458238947528346283745802837468238947520137489572463589 mpz_set_str 12394872039846520983745092837458238947528346283745802837468238947520137489572463589 mpz_add 12394872079693041967490185674916477895056692567491605674936477895040274979144927178 |
mpz_add(c, a, b)で多倍長と多倍長の加算ができます。
今回の場合aとbを足したものがcに格納されます。
mpz_add_uiで多倍長とunsigned int型の加算もできます。
減算
1 2 3 4 5 |
mpz_sub(c, a, b); gmp_printf ("mpz_sub %Zd\n", c); mpz_sub_ui(c, a, 100000000000); gmp_printf ("mpz_sub %Zd\n", c); |
1 2 |
mpz_sub 12394872000000000000000000000000000000000000000000000000000000000000000000000000000 mpz_sub 12394872039846520983745092837458238947528346283745802837468238947520137389572463589 |
記述は加算とほぼ同じです。
乗算
1 2 3 4 5 |
mpz_mul(c, a, b); gmp_printf ("mpz_mul %Zd\n", c); mpz_mul_ui(c, a, 100000000000); gmp_printf ("mpz_mul %Zd\n", c); |
1 2 |
mpz_mul 493892528826579740856449678153709185112968648756875597296626086187222959217877299235777833957580112237095599379483147967606614656277146234780490602730760921 mpz_mul 1239487203984652098374509283745823894752834628374580283746823894752013748957246358900000000000 |
除算
1 2 3 4 5 |
mpz_cdiv_q(c, a, b); gmp_printf ("mpz_cdiv_q %Zd\n", c); mpz_cdiv_q_ui(c, a, 100000000000); gmp_printf ("mpz_cdiv_q %Zd\n", c); |
1 2 |
mpz_cdiv_q 311065352 mpz_cdiv_q 123948720398465209837450928374582389475283462837458028374682389475201375 |
剰余
1 2 3 4 5 |
mpz_mod(c, a, b); gmp_printf ("mpz_mod %Zd\n", c); mpz_mod_ui(c, a, 100000000000); gmp_printf ("mpz_mod %Zd\n", c); |
ひとまず普段プログラミングをしていてよく使う演算について触れました。
他にも演算関数が用意されていますが、それはその都度使い方を覚えていけばいいかなと思います。
c++から使う
c++からも使うことができます。
c++にはクラスが用意されていて、c言語からよりも使いやすいかもしれません。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
#include <gmpxx.h> #include <iostream> using namespace std; int main (void) { mpz_class a, b, c; a = "1234567890987654321"; b = 123456789; c = a+b; cout << "add " << c << "\n"; c = a-b; cout << "sub " << c << "\n"; c = a*b; cout << "mul " << c << "\n"; c = a/b; cout << "div " << c << "\n"; c = a%b; cout << "mod " << c << "\n"; return 0; } |