吟遊詩人の素数探索その3〜python使ってリュカ・レーマー〜

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

前回表計算ソフト上でリュカ・レーマーテストをやったところ、31ビットの計算がうまく行きませんでした。

19ビットの計算はできたので、文明レベルは1588年のピエトロ・カタルディと言ったところです。

https://ginyusizin.com/2019/11/09/0017/

そこで今回はpython使ってリュカ・レーマーテストをしてみます。

使ったバージョンはUbuntu18に最初から入っていたPython 3.6.8です。

最新バージョンは3.8らしいですが……まあ、動けばいいんだよ。

Pythonのプログラミングはほぼ初めてです。(前にちょっとだけ使ったことがあるような無いような)

型とか指定しなくてもいいのですごく楽ですよね。でも「こんなんで大丈夫?」と書いてて心配になる。言語が高級すぎる。

今回のリュカ・レーマーテストの実装がこちら

(関数の中身はこちらの記事を参考にしてます:https://qiita.com/POPOPON/items/a35f94a7826dae9ce61c

p=3~3000の範囲で2個飛ばしで素数を探索しています。実行時間も表示するようにしています。

で、実行結果がこちら

お、お、ちゃんと出来てる。

17番目のメルセンヌ素数まで探索できていますね。1952年のラファエル・M・ロビンソンに追いつきました。1夜にして400年の進歩です。

約10秒ほどで3000ビットまで探索できています。元記事(https://qiita.com/POPOPON/items/a35f94a7826dae9ce61c)では、古いノートPCを使って50秒ほどとのことなので、約5倍の処理時間ですね。

次に、今度はちょっとずるをして、あらかじめ26番目までのメルセンヌ数を与えるpを与えて、その判定をしてみます。

実行時間は各メルセンヌ素数のリュカ・レーマーテストにかかった時間にしてます。

実行結果はこちら

2〜17番目まで
18~21番目まで
21〜22番目
23番目
24番目
25番目
26番目

1画面に収まりきらなくなってきたから……やめようね。

現在51あるメルセンヌ素数の26番目までやってきました(ズルしてだけど)

1979年のランドン・カート・ノルまで追いつきました。

しかしさすがpython,適当に記述してもちゃんと23209ビットの整数型で表示してくれるとは・・・・・・やりますねぇ!

2ビットの計算では1マイクロ秒程度で終わっていましたが、23209ビットでは23秒かかっていますね。

実行時間の増え方を見てみましょう。

横軸にメルセンヌ素数のビット数、縦軸に実行時間を描いています。

指数関数的に増加しているわけではないようですが、ビット数の2乗に比例しているようです。(リュカレーマーテストの実行速度がO(N^2)らしいのでその関係かな?参考:http://intmain.hatenablog.com/entry/2016/12/29/023549

最終的には2147483647ビットの計算をしたいので、21億×21億×5.68×10^-8≒2.5千億秒(8000年?)かかることになります。

・・・・・・これは厳しい。

1億桁の素数を見つけて早期退職したいのに、その前に定年が来てしまう……。

リュカ・レーマーテストを高速化する必要がありますね。

剰余算をビット演算にすることで高速化可能らしいですが、どの程度早くなるのでしょうか?(そもそもPythonの剰余算がそこそこ最適化されている可能性があるし)

GPUも使えたら使っていきたいですが、……並列処理ってある?

あと、p=2147483647を入力したところ、メモリエラーで弾かれました。

21億ビットのメモリの扱いをどうするかも課題ですね。

リュカ・レーマーテストを超える高速な素数判定法が必要かもしれません。

ええ!リュカ・レーマーテストより早く素数を判定!?

できらぁ!リュカ・レーマーテストより早く素数を判定するって言ってんだよ!

え!リュカ・レーマーテストより早く素数を判定!?

次回は気が向いたらビット演算しようかなと思います。だいぶ先になると思います。

つづけ

(P.S.昨夜から33番目のメルセンヌ素数(p=859,433)を探しに行ったリュカ・レーマーテストが帰ってきてません。誰かなんとかしてください。)

コメントを残す

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

WordPress.com ロゴ

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

Google フォト

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

Twitter 画像

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

Facebook の写真

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

%s と連携中