Go to Qiita Advent Calendar 2024 Top
LoginSignup
42
32

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

@tubo28

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

Last updated at Posted at 2015-08-20

tl; dr

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

install
# 手元の環境にインストール (Ubuntu の場合)
$ sudo apt-get install libboost-all-dev
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;
}
output
$ g++ tldr.cc -std=c++17
$ ./a.out
217010269916637997123670675597563196
3.14159265358979323846264338327950288419716939937511

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

はじめに ～ 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 は、それぞれ多倍長整数と多倍長浮動小数点数の歴史あるライブラリです。ここでは説明しないので、この記事の情報元の下記サイトを見てください。

サンプル

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

$ sudo apt-get install libboost-all-dev

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

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 にそのまま提出してもコンパイルエラーにはならないはずです。
実際に手元でコンパイルして実行してみます。

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

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

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 と AtCoder で Boost ライブラリが使えるようになりました。したがって、これらのサイトでは多倍長が無いがために他の言語を選択しなくてはいけないということが少なくなったと思われます。

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

おわりに

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

42
32
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
42
32

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?