吟遊詩人の素数探索その4〜gmpy使ったらメッチャ速くなった話〜

どうも吟遊詩人です。今回も素数探索、やっていきますよ。

前回、pythonでリュカレーマーテストやったら２６番目のメルセンヌ素数まで素数判定できました。

前回：https://ginyusizin.com/2019/11/10/0018/

あの後も計算を回して、31番目のメルセンヌ素数までは素数判定することができました。（３３番目探しに行った子は結局３日待っても帰ってきませんでした。）

今回はこちらの記事（ http://intmain.hatenablog.com/entry/2016/12/29/023549 ）を参考に剰余算をビット演算に換え……ようと思ったのですが、その前に気づいたことがあって。

この記事だと３０番目のメルセンヌ素数のリュカレーマーテストが２分44秒で終わってるんですよね……。（ビット演算にする前に）

前回のプログラムだと、30番目のメルセンヌ素数は１時間以上判定に時間がかかっています。

なんでこんな時間に差があるのかと思ったら、どうやらこの記事では、2乗の計算にGMPというライブラリを使っているようでした。

GMPとは？

GMP(GNU Multiple Precision library)とは任意精度計算ライブラリの一つです。GMPを使うと、変数単位で精度を指定することができ、上記のような計算精度の問題が解決できます。

引用元： http://pyopyopyo.hatenablog.com/entry/20090303/p1

pythonでは前回のコードのように型を指定しなくても勝手に任意長の変数にしてくれていましたが、桁数の多い計算をGMPを用いると高速化できるようです。

python用のGMPライブラリはgmpyというもので、python3にgmpy2を早速入れてみました。導入の仕方はこちらの記事( https://qiita.com/nendocode/items/a90af33020d33d9fd386 )を参考にしました。

そして今回gmpy2を取り入れたコードがこちら↓↓

２乗のところをmpz(s)**2としています。**の演算子がmpzによってオーバーライドされるそうです。

そして計算の結果、実行時間がこちら。

はやっ！！

青いドットが前回ので、赤いドットが今回gmpyを使ったものです。

メッチャ速くなりました。

30番目のメルセンヌ素数の判定は２分強で終わったので、だいたい元記事ともコンパラですね。

（ちなみに(mpz(s)**2-2)%Mの代わりにpow(mpz(s),2,M)-2もやりましたが、pow使ったほうが遅かったです。）

gmpyすごいですね、ちなみに2^2147483647を計算したら0.28秒で答えが出ました。普通に計算するといつまでたっても答えが出力されないのに。

とにかくgmpy使っただけでメッチャ速くなるので、皆さんも大きな桁の計算する時はぜひ使ってくださいね。

無事３３番目のメルセンヌ素数も超え、３５番目まで来ました。

（３５番目のメルセンヌ素数はp=1,398,269, 1996年 に GIMPS / Joel Armengaud によって発見されています。）

次回は剰余算のところをビット演算化します。

次回で吟遊詩人の素数探索第一部完です。

お楽しみに

（余談：素数探すついでにpython始めようとpythonで書いてたけど、速度を求めるなら普通にCで書いたほうが良かったかも（元記事もC++だったし）、今更だけど。気が向いたらそのうちCでも書いて速度比較しようかな……。）

つづく

• WordPress
• Facebook
• Twitter