読者です 読者をやめる 読者になる 読者になる

Boost.Multiprecision 多倍長整数

C++

Boost 1.53.0から、多倍長演算ライブラリであるBoost.Multiprecisionが入りました。
このライブラリは、整数と浮動小数点数をサポートしていますが、今回は整数の方を紹介します。


以下は、多倍長整数で階乗を求める例です。

#include <iostream>
#include <boost/multiprecision/cpp_int.hpp>

using namespace boost::multiprecision;

int main()
{
    // 128ビット整数
    int128_t v = 1;

    // 20の階乗を求める
    for (unsigned i = 1; i <= 20; ++i)
       v *= i;

    std::cout << v << std::endl;

    // 任意精度整数
    cpp_int u = 1;

    // 100の階乗を求める
    for (unsigned i = 1; i <= 100; ++i)
       u *= i;

    std::cout << u << std::endl;
}
2432902008176640000
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

Boost.Multiprecisionでは、固定精度整数と任意精度整数が提供されます。
固定精度整数としては、128ビットの符号あり整数であるint128_t、256ビットのint256_t、512ビットのint512_t、1024ビットのint1024_tが定義されます。また、符号なし版でuint128_tなどが定義されます。
それに加えて、任意精度整数としてcpp_int型が定義されます。任意精度の方は、メモリが許す限り無限の長さの整数を扱えます。


固定精度整数は、任意精度整数の制限版として定義され、ユーザーが任意の固定精度整数を定義できます。これらの整数型は、以下のように定義されます:

namespace boost{ namespace multiprecision{

...

template <unsigned MinDigits = 0,
          unsigned MaxDits = 0,
          cpp_integer_type SignType = signed_magnitude,
          cpp_int_check_type Checked = unchecked,
          class Allocator = std::allocator<limb_type> >
class cpp_int_backend;

...
typedef number<cpp_int_backend<> > cpp_int;
typedef number<cpp_int_backend<128, 128, unsigned_magnitude, unchecked, void> > uint128_t;
typedef number<cpp_int_backend<128, 128, signed_magnitude, unchecked, void> > int128_t;
}}

typedefを自分で定義すれば、アロケータもユーザー定義のものを使用できます。


参照:
cpp_int - Boost Multiprecision Library
gmp_int - Boost Multiprecision Library
tom_int - Boost Multiprecision Library