Boostの多倍長整数ライブラリ

　Boostの多倍長整数ライブラリを使ってみました。これでCode JamとかHacker Cupで多倍長出てもC++で行けそうです。

準備

自宅のマシンはLinuxなので最初からBoostが入っていましたが、versionが少し古くて目的の機能は使えませんでした。

ということでインストールから。

1. 最新版のBoostを公式ページからダウンロードします。

2. ダウンロードしたら適当なディレクトリに展開します。

3. 展開したディレクトリに移動して以下のコマンドを実行します。

kenjih$ ./bootstrap.sh --prefix=/home/kenjih/local
kenjih$ ./b2 install 

--prefixで指定しているのは、インストール先のディレクトリです。Linuxのディストリビューションに最初から入っているBoostの上にインストールすると、環境が壊れてしまう可能性があるため、ユーザのlocalディレクトリなどにインストールするのがよいと思います。

使ってみる

まずは、簡単な掛け算から入ってみます。入力された2つの整数の積を計算してみます。

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

using namespace std;

typedef boost::multiprecision::cpp_int bigint;

int main() {
    bigint a, b;

    cin >> a >> b;
    cout << a * b << endl;

    return 0;
}

コンパイルするときは、以下のようにheaderの検索パスを指定します。

kenjih$ g++ -o test -I ~/local/include test.cpp

次に、フィボナッチ数列でも計算してみますか。フィボナッチ数列の最初の100項を表示します。

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

using namespace std;

typedef boost::multiprecision::cpp_int bigint;

int main() {
    bigint x(0), y(1);

    for (int i = 0; i < 100; i++) {
        cout << x << endl;
        y = y+x;
        x = y-x;
    }

    return 0;
}

 最後に、ビット演算。入力された数を2進数で解釈して再構築できるか確認しています。

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

using namespace std;

typedef boost::multiprecision::cpp_int bigint;

int main() {
    bigint x, y, b(1);
    cin >> x;

    while (x > 0) {
        if (x & 1)
            y |= b;
        x >>= 1;
        b <<= 1;
    }
    
    cout << y << endl;

    return 0;
}