Help us understand the problem. What is going on with this article?

C++ の多倍長整数型・多倍長浮動小数点数型 : boost::multiprecision の使い方メモ

tl; dr

AtCoder と AOJ では次のようなコードを書くと多倍長整数と多倍長小数が使えます。
ただし、多倍長演算がボトルネックで TLE になるときは、専用の高速なライブラリを利用している言語 (Ruby など) で書き直したほうが速いこともありえます。

tldr.cc
#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/multiprecision/cpp_int.hpp>
#include <iostream>

int main() {
  using namespace std;
  namespace mp = boost::multiprecision;
  // 任意長整数型
  using Bint = mp::cpp_int;
  // 仮数部が1024ビットの浮動小数点数型(TLEしたら小さくする)
  using Real = mp::number<mp::cpp_dec_float<1024>>;

  Bint a = 546534242;
  Bint b("238431313536543513515132513213516353");
  Bint c("365435435435135435143548546841324135");
  cout << a * b % c << endl;

  Real d = -1.0;
  cout << fixed << setprecision(50) << acos(d) << endl;
}
output
217010269916637997123670675597563196
3.14159265358979323846264338327950288419716939937511

より詳しい使い方はこちら

C++ の多倍長整数型・多倍長浮動小数点数型

C++ には標準ライブラリに多倍長整数がありません。したがって、大きな整数を扱う必要があるときは boost::multiprecision などの外部ライブラリを使うことになります。高精度な浮動小数点数型が必要なときも同様です。

いつも使い方を忘れてググっているので、自分用にコピペしてすぐ使えるコードを残しておきたく、記事にしてみました。

ライブラリの選択肢

Boost ライブラリには

(1) Boost 独自実装の C++ ヘッダライブラリ
(2) より高速な GMP や MPFR といった外部ライブラリのラッパ

があります。手軽かつオンラインジャッジでも使えるのは (1) のみで、include するだけで使えます。整数型は cpp_int、浮動小数点数型は cpp_dec_float という名前がつけられています。AtCoder や AOJ などの Boost が使えるオンラインジャッジで使えます。
(2) はコンパイル時に依存ライブラリをリンクする必要があるため使えません。ここでは説明しないので、下記のサイト (この記事の情報元) を見てください。

サンプル

例として、次のようなプログラムを書いたとします。

main.cc
#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/rational.hpp>
#include <iostream>

int main() {
  using namespace std;
  namespace mp = boost::multiprecision;
  // 任意長整数型
  using Bint = mp::cpp_int;
  // 仮数部長が32の浮動小数点数型
  using Real32 = mp::number<mp::cpp_dec_float<32>>;
  // 仮数部長が1024の浮動小数点数型
  using Real1024 = mp::number<mp::cpp_dec_float<1024>>;
  // 有理数型
  using Rat = boost::rational<Bint>;

  {
    cout << "Trying mp::cpp_int" << endl;
    Bint a = 1;
    for (int i = 1; i <= 100; i++)
      a *= i;
    cout << "       100! = " << a << endl;
    cout << endl;
  }
  {
    cout << "Trying mp::number<mp::cpp_dec_float<32>>" << endl;
    Real32 a = 1;
    for (int i = 1; i <= 100; i++)
      a /= i;
    cout << "     1/100! = " << scientific << setprecision(50) << a << endl;
    for (int i = 1; i <= 100; i++)
      a *= i;
    cout << "1/100!*100! = " << scientific << setprecision(50) << a << endl;
    cout << endl;
  }
  {
    cout << "Trying mp::number<mp::cpp_dec_float<1024>>" << endl;
    Real1024 a = 1;
    for (int i = 1; i <= 100; i++)
      a /= i;
    cout << "     1/100! = " << scientific << setprecision(50) << a << endl;
    for (int i = 1; i <= 100; i++)
      a *= i;
    cout << "1/100!*100! = " << scientific << setprecision(50) << a << endl;
    cout << endl;
  }
  {
    cout << "Trying rational number type with mp::cpp_int" << endl;
    Rat a(1, 1); // 1/1
    for (int i = 51; i <= 100; i++)
      a *= Rat(i, i - 50); // i/(i-50)
    assert(a.denominator() == 1);
    cout << "  C(100,50) = " << a.numerator() << endl;
    cout << endl;
  }
}

AtCoder と AOJ にそのまま提出してもコンパイルエラーにはならないはずです。
実際に手元でコンパイルして実行してみます。事前に Boost ライブラリをインストールしておく必要があります。

# sudo apt install libboost-all-dev
g++ main.cc -std=c++11 -O2
./a.out

次のような出力が得られます。

Trying mp::cpp_int
       100! = 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

Trying mp::number<mp::cpp_dec_float<32>>
     1/100! = 1.07151028812546692318354675951919152202019804840857e-158
1/100!*100! = 1.00000000000000000000000000000000000000807962294700e+00

Trying mp::number<mp::cpp_dec_float<1024>>
     1/100! = 1.07151028812546692318354675951919152201154064929271e-158
1/100!*100! = 1.00000000000000000000000000000000000000000000000000e+00

Trying rational number type with mp::cpp_int
  C(100,50) = 100891344545564193334812497256

整数 $100!$ が正確に計算できています。$1$ に対して $100!$ で割ってまた掛けた値を $10^{-50}$ の単位まで表示してみると、仮数部が 32 ビットだと誤差が現れていますが、1024 ビットも取ると現れていませんね。

実行速度に関してはベンチマークを取りたいところですが面倒なので各自お願いします。cpp_intcpp_dec_float はあまり速くありません。プリミティブ型と比べるとかなり遅く、前述した GMP などのライブラリよりも多少遅いと思います (カリカリにチューニングされているらしい)。

余談

この記事を最初に書いた時分は、競技プログラミングで C++ を使っていて多倍長が必要になったら自分で書いたライブラリ(スニペット)を貼り付けるか、別の言語を使う以外の方法がありませんでした。しかし今では AOJAtCoder で Boost ライブラリが使えるようになりました。したがって、これらのサイトでは多倍長が無いがために他の言語を選択しなくてはいけないということが少なくなったと思われます。

ところが、オンラインジャッジでは普通 C++ から GMP 等の速いライブラリが呼べないので、従来どおり、デフォルトで GMP を使用する Ruby などを使った方が速いこともありえます。どうしても使いたければ、C++ から dlopen 関数を使うなどして無理やり呼び出す汚い手法も知られているので興味がある方は自己責任で調べてみてはどうでしょうか。それほど高速に多倍長整数を処理する必要がある問題は yukicoder (ネタバレ注意) でしか見たことがありませんが…

まとめ

便利な世の中になりましたねえ

Why do not you register as a user and use Qiita more conveniently?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away