C++ の多倍長整数型・多倍長浮動小数点数型 : boost::multiprecision の競技プログラミングでの使い方メモ

## tl; dr

AtCoder と AOJ では次のようなコードを書くと多倍長整数と多倍長浮動小数点数が使えます。
つまり、メモリが許す限り無限に大きい/小さい整数と double や long double より精密な浮動小数点数が扱えます。
ただし遅いので、多倍長演算がボトルネックで TLE になることもありえます。そのようなときはより高速なライブラリである GMP を元から利用している言語 (Ruby など) で書き直したほうがいいです。

```shell:install
# 手元の環境にインストール (Ubuntu の場合)
$ sudo apt-get install libboost-all-dev
```

```cpp:tldr.cc
#include <iostream>
using namespace std;

// 多倍長テンプレ
/* ---------------------- ここから ---------------------- */
#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/multiprecision/cpp_int.hpp>
namespace mp = boost::multiprecision;
// 任意長整数型
using Bint = mp::cpp_int;
// 仮数部が10進数で1024桁の浮動小数点数型(TLEしたら小さくする)
using Real = mp::number<mp::cpp_dec_float<1024>>;
/* ---------------------- ここまで ---------------------- */

int main() {
  // 整数
  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;
}
```

```shell:output
$ g++ tldr.cc -std=c++17
$ ./a.out
217010269916637997123670675597563196
3.14159265358979323846264338327950288419716939937511
```

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

- [多倍長整数 - boostjp](https://boostjp.github.io/tips/multiprec-int.html)
- [多倍長浮動小数点数 - boostjp](https://boostjp.github.io/tips/multiprec-float.html)

## はじめに ～ C++ の多倍長整数型・多倍長浮動小数点数型

C++ には標準ライブラリに多倍長整数がありません。したがって、桁が大きな整数を扱うには `boost::multiprecision` などの外部ライブラリが必要です。高精度な浮動小数点数型が必要なときも同様です。Boost は AtCoder と AOJ でも使えるので、競技プログラミングでも現実的な選択肢です。

この記事では、`boost::multiprecision` の簡単な使い方を紹介をします。

## Boost ライブラリにおける選択肢

Boost ライブラリには

1. Boost 独自実装の整数・浮動小数点数
2. より高速な GMP や MPFR といった動的ライブラリのラッパ

があります。

1 つ目は手軽で include するだけで使えます。整数型は `cpp_int`、浮動小数点数型は `cpp_dec_float` という名前がつけられています。AtCoder や AOJ などの Boost が使えるオンラインジャッジでも使えます。

2 つ目はコンパイル時に依存ライブラリをリンクする (コマンドで与える) 必要があるためオンラインジャッジでは使えません。GMP と MPFR は、それぞれ多倍長整数と多倍長浮動小数点数の歴史あるライブラリです。ここでは説明しないので、この記事の情報元の下記サイトを見てください。

- [多倍長整数 - boostjp](https://boostjp.github.io/tips/multiprec-int.html)
- [多倍長浮動小数点数 - boostjp](https://boostjp.github.io/tips/multiprec-float.html)

## サンプル

まず Boost をインストールします。Ubuntu では次のようにします。

```shell
$ sudo apt-get install libboost-all-dev
```

例として、次のようなプログラムを `main.cc` に保存します。

```cpp:main.cc
#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/rational.hpp>
#include <iostream>
using namespace std;
namespace mp = boost::multiprecision;
// 任意長整数型
using Bint = mp::cpp_int;
// 仮数部が32桁(10進数)の浮動小数点数型
using Real32 = mp::number<mp::cpp_dec_float<32>>;
// 仮数部が1024桁(10進数)の浮動小数点数型
using Real1024 = mp::number<mp::cpp_dec_float<1024>>;
// ついでに有理数型
using Rat = boost::rational<Bint>;

int main() {
  {
    cout << "Try mp::cpp_int" << endl;
    Bint a = 1;
    for (int i = 1; i <= 100; i++)
      a *= i;
    cout << "       100! = " << a << endl;
    cout << endl;
  }
  {
    cout << "Try 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 << "Try 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 << "Try 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 にそのまま提出してもコンパイルエラーにはならないはずです。
実際に手元でコンパイルして実行してみます。

```shell
$ g++ main.cc -std=c++17 -O3
$ ./a.out
```

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

```text:stdout
Try mp::cpp_int
       100! = 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

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

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

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

```

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

## 実行速度

ベンチマークを取りたいところですが手抜きをして省きます。`cpp_int` と `cpp_dec_float` はあまり速くありません。GMP よりも確実に遅く (GMP はカリカリにチューニングされているらしい)、プリミティブ型よりかなり遅いです。私の体感で `double` の数十倍くらい？です。大きいテストケースを手元で実行すると明らかな遅さが実感できると思います。まあ、桁数分の数列を保持していることを考えれば当たり前でしょう。

## 余談

この記事を最初に書いた時分は、競技プログラミングで C++ を使っていて多倍長が必要になったら自分で書いたライブラリ（スニペット）を貼り付けるか、別の言語を使う以外の方法がありませんでした。しかし今では [AOJ](http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2717279) と [AtCoder](https://language-test-201603.contest.atcoder.jp/) で Boost ライブラリが使えるようになりました。したがって、これらのサイトでは多倍長が無いがために他の言語を選択しなくてはいけないということが少なくなったと思われます。

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

## おわりに

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