【C++】GMPで大きめの数字（主に整数）を使ってみる

近年では、AIや機械学習の進展とともに、低精度で演算効率を高めるということも多いと思いますが、今回はその逆のお話。C++で64-bit以上の数値を扱ってみよぜっていう話をしようと思います。今回使用するGMPの公式ドキュメントが豊富でわかりやすい代わりに、資料が思いの外少ないというのもあり、このテーマで投稿することにしました。

アドベントカレンダーにふさわしくないのはﾕﾙｼﾃ

GMPとは

GMP(NU Multi-Precision Library)とは、多倍長整数ライブラリと呼ばれるライブラリの一種です。CやC++などを中心に、多くのプログラミング言語では数値を変数や定数としてメモリに格納する時、最大値が64-bitあるいは128-bitに固定されますが、このライブラリを使えば、その数の大きさをメモリが許容するまで大きくすることができます。

演算の精度や自由度が高まる代わりに、レジスタではなくメモリに値を格納することもあるので、演算速度が標準ライブラリよりも劣化するという問題はありますが、リアルタイム性を求められないのであれば使う価値はあると思います。

今回はC++で扱いますが、GMPは主にCでも使われており、RustやPythonなどでもそれ用のライブラリというかラッパーが用意されている他、Rubyに至ってはそもそも機能として組み込まれているようですね。このあたりについてはまたゆっくりと。

公式が用意している英語のドキュメントと、有志の方が翻訳してくれている日本語のドキュメントがあります。本体バージョンが6.3であるのに対して、日本語のドキュメントは6.1.2とやや古く、少し異なる使用も登場しているため、使用する際は公式のドキュメントを参考にすると良いと思います。

環境

• デバイス：MacBook Air Late 2020（M1）
• OS：macOS Sequoia 15.1
• GCC 14
• GMP 6.3.0

今回はとりあえずMac環境で行いますが、LinuxやWindows環境でも使えます。ただ、WindowsでやるならWSLなどでLinuxを動かしてやったほうがいいとは思います。

また、昨年の夏にApple Silicon Macにも対応したので、結構簡単に動きます。

インストール

インストールは各パッケージマネージャーから行えます。MacならHomebrewにあります。もしかしたら、Ubuntuならbuild-essential入ってる・・・かも（いくつかのパッケージでは依存関係だったかも）。

brew install gmp

コンパイルの際は、

g++ -o tmp -g ./main.cpp -lgmp -lgmpxx

基本的な部分

CとC++でGMPの記法が若干異なります。Cの記法はC++でも使えますが、個人的にはC++の記法のほうが書きやすくていいと思います。特段の理由がなければC++で書くことをおすすめします。

ひとまず、long longを飛び出して見ましょう。

#include<iostream>
#include<gmp.h>
#include<gmpxx.h>

int main(){
    mpz_class mpz_x;

    mpz_x = "115792089237316195423570985008687907853269984665640564039457584007913129639936";

    std::cout << mpz_x << std::endl;

    return 0;
}

まず、mpz_classの説明はおいておきまして、まず2^256という普通のC++では扱えない数値を用意しました。一回試しにunsigned long longに代入してみたところ「大きすぎる」と言われました。これを実行しますと、しっかりとこの値が出力されます。

つまり、mpz_classに256-bitの値が格納できたということですね。めでたし、めでたし。

一応、mpz_class mpz_x("115..(中略)..36");のように宣言と同時に初期化することもできます。

では、mpz_classについて。mpz_class型はC++のGMP（gmpxx.h）に用意されている、多倍長整数を格納するためのクラスでして、整数演算なら基本的にはこれがベースになります。mpz_classでは、mpz_x = "123"のように、=を使って値を代入することが可能です。残念ながらCではこの記法が利用できないため、やや回りくどい書き方になってしまいます。

mpz_class型で宣言した変数についても、他の型の変数と同様にcoutを使って標準出力が可能です。cout優秀。

出力のときの注意点

桁が大きすぎたりすると、何故か桁数がカットされてしまうことがあります。一応内部では値をしっかりと維持しているようなので、そのまま演算を続ける分には問題ないと思いますが、出力するときには気を付けて見てあげてください。

私の場合、std::flushを使用することで解決できました。

#include<iostream>
#include<gmp.h>
#include<gmpxx.h>
#include<string>

int main(){
    mpz_class x("123456789123456789123456789123456789");
    mpz_class y("987654321987654321987654321987654321");

    std::cout << lcm(x,y) << std::flush;

}

浮動小数点数を扱う

GMPは全体に共通してmpzが整数を意味しています。一方で浮動小数点数についてはmpfとなります。つまり、mpf_classを使えばいいわけですね。

#include<iostream>
#include<gmp.h>
#include<gmpxx.h>
#include<string>

int main(){

    mp_exp_t base;
    mpf_set_default_prec(256);
    mpf_class mpf_x;

    mpf_x = "0.1234567891234567891234567891";

    mpf_out_str(stdout,10,50,mpf_x.get_mpf_t());

    std::cout << std::endl;
}

浮動小数点はどんなときでも整数ほどすんなりとは扱えませんね。少し回りくどくなってしまっています。まずmpf_class自体は、mpz_class同様多倍長浮動小数点を意味していますが、mpf_set_default_precで制度をあらかじめ指定しています（今回は256bit）。

出力はmpf_out_strを使用しています。coutでも出力できますが、桁数が切り上げられてしまいますし、それを訂正するのもやや回りくどくなってしまっていますので、稚拙ですがこのような形にしました。std::flushを使ってもいいかもしれません。

mpf_out_strの引数は順に、ストリーム・基数・桁数・mpf_t型での対象の浮動小数点となります（mpf_tについては後述）。

今回は、小数点数についても取り上げてしまうときりがないので、主に整数を中心に扱うことにします。

Cの関数を使う

mpz_classやmpf_classをはじめとしたGMPのC++の機能はgmpxx.hが提供していますが、gmp.hで定義されるようなCの機能も使用することができます。

しかし、C向けに定義された関数では引数がmpz_t型やmpf_t型で定義されているため変換が必要です。これらの型はCでGMPを使用する際に利用する型です。

そこで使用するのがmpz_classとmpf_classのメンバ関数であるget_mpz_tとget_mpf_tです。mpz_tやmpf_tを要求されたときも、このメンバ関数を使えばOKです。

例えば、平方根を計算する時にgmpxx.hでもsqrtが定義されていますが、gmp.hで定義されているmpz_sqrtを使用することも可能です。サンプルを見てみましょう。

mpz_class x("123456789123456789123456789");
mpz_class result; // 結果を格納する変数

// 平方根の計算
mpz_sqrt(result.get_mpz_t(),x.get_mpz_t());

std::cout << result << std::endl;

mpz_sqrtは、第1引数も第2引数もmpz_t型を要求しますが、get_mpz_t()メンバ関数を使用することで、mpz_class型変数でも利用可能になります。少し長ったらしくなりますが・・・。

演算

以下、ヘッダー等省略します。

さて、GMPで演算をしますが、四則演算（+剰余算）については普通のC++と同様に演算子を使えばOKです。

mpz_class x("123456789123456789123456789");
mpz_class y("987654321987654321987654321");

std::cout << x + y << std::endl;

結果が出力されます。四則演算はとりあえずこれでOK

では、cmathで定義されるような演算についてはどうすればいいのか。この点はさすがGMP。便利な関数が用意されているのです。

平方根

# mpz_classの関数を使用する場合
mpz_class x("123456789123456789123456789");
std::cout << sqrt(x) << std::endl;

最大公約数・最小公倍数

桁がカットされたので、mpz_out_strを使用しています。

mpz_class x("123456789");
mpz_class y("987654321");
mpz_class result;

// 最小公倍数
result = lcm(x,y);
mpz_out_str(stdout,10,result.get_mpz_t());   

//最大公約数
result = gcd(x,y);
mpz_out_str(stdout,10,result.get_mpz_t());

【実践】クソデカ数字を素因数分解する

実践的なコードとして、与えた数字を素因数分解するコードを書いてみました。

mpz_class CompositeNumber, d , q;

// 素因数分解する数字
CompositeNumber = "1234567891234567891234567890";

std::cout << CompositeNumber << " = ";
while(CompositeNumber >= 4 && CompositeNumber % 2 == 0){
    std::cout << "2 * "; 
    CompositeNumber /= 2;
}

d = 3;
q = CompositeNumber / d;

while(q >= d){
    if(CompositeNumber % d == 0){
        std::cout << d << " * ";
        CompositeNumber = q;
    }else{
        d += 2;
    }
    q = CompositeNumber / d;
}

std::cout << CompositeNumber;

return 0;

まとめ

アドベントカレンダー1日目の開幕に研究で役立ったGMPライブラリについて紹介しました。シンプルに思ったより情報が少なかったので、書いてみました。

プログラムの導入部分さえわかってしまえば、あとは公式ドキュメントを見ながら色々実装できると思います！是非どうぞ！

アドベントカレンダー、他の人が許すなら別のテーマでまた書きます！

ちなみに、桁数をバカみたいに増やすと、しっかり演算時間がかかりますのでご注意を。