c言語でGMPを使って多倍長演算

c言語で標準では多倍長整数がサポートされていないのでこれらを扱いたい場合は自分で実装するかライブラリーを使う必要があります。

そこで今回はGMP(GNU Multi-Precision Library)という算術ライブラリを利用して多倍長整数を使ってみたいと思います。
https://gmplib.org/manual/index.html

片っ端からやっていってもきりがないので必要そうなところを触れておきたいと思います。

1 コンパイル
2 変数の初期化
3 演算
4 c++から使う

コンパイル

コンパイルは以下のように行います。

gcc gmp_sample.c -o gmp_sample -lgmp

変数の初期化

#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型も割り当てることができます。

演算

加算

#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;
}

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型の加算もできます。

減算

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);

mpz_sub 12394872000000000000000000000000000000000000000000000000000000000000000000000000000
mpz_sub 12394872039846520983745092837458238947528346283745802837468238947520137389572463589

記述は加算とほぼ同じです。

乗算

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);

mpz_mul 493892528826579740856449678153709185112968648756875597296626086187222959217877299235777833957580112237095599379483147967606614656277146234780490602730760921
mpz_mul 1239487203984652098374509283745823894752834628374580283746823894752013748957246358900000000000

除算

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);

mpz_cdiv_q 311065352
mpz_cdiv_q 123948720398465209837450928374582389475283462837458028374682389475201375

剰余

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言語からよりも使いやすいかもしれません。

#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;
}