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

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

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

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

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

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

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

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

なんでこんな時間に差があるのかと思ったら、どうやらこの記事では、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を取り入れたコードがこちら↓↓

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

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

はやっ!!

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

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

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

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

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

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

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

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

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

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

お楽しみに

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

つづく

吟遊詩人の素数探索その4〜gmpy使ったらメッチャ速くなった話〜” への1件のフィードバック

コメントを残す

以下に詳細を記入するか、アイコンをクリックしてログインしてください。

WordPress.com ロゴ

WordPress.com アカウントを使ってコメントしています。 ログアウト /  変更 )

Google フォト

Google アカウントを使ってコメントしています。 ログアウト /  変更 )

Twitter 画像

Twitter アカウントを使ってコメントしています。 ログアウト /  変更 )

Facebook の写真

Facebook アカウントを使ってコメントしています。 ログアウト /  変更 )

%s と連携中