どうも吟遊詩人です。今回も素数探索、やっていきますよ。
前回表計算ソフト上でリュカ・レーマーテストをやったところ、31ビットの計算がうまく行きませんでした。
１９ビットの計算はできたので、文明レベルは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個飛ばしで素数を探索しています。実行時間も表示するようにしています。
で、実行結果がこちら
お、お、ちゃんと出来てる。
１７番目のメルセンヌ素数まで探索できていますね。1952年のラファエル・M・ロビンソンに追いつきました。１夜にして4００年の進歩です。
約10秒ほどで3000ビットまで探索できています。元記事（https://qiita.com/POPOPON/items/a35f94a7826dae9ce61c）では、古いノートPCを使って50秒ほどとのことなので、約5倍の処理時間ですね。
次に、今度はちょっとずるをして、あらかじめ26番目までのメルセンヌ数を与えるpを与えて、その判定をしてみます。
実行時間は各メルセンヌ素数のリュカ・レーマーテストにかかった時間にしてます。
実行結果はこちら
１画面に収まりきらなくなってきたから……やめようね。
現在51あるメルセンヌ素数の26番目までやってきました（ズルしてだけど）
1979年のランドン・カート・ノルまで追いつきました。
しかしさすがpython,適当に記述してもちゃんと２３２０９ビットの整数型で表示してくれるとは・・・・・・やりますねぇ！
２ビットの計算では1マイクロ秒程度で終わっていましたが、２３２０９ビットでは２３秒かかっていますね。
実行時間の増え方を見てみましょう。
横軸にメルセンヌ素数のビット数、縦軸に実行時間を描いています。
指数関数的に増加しているわけではないようですが、ビット数の２乗に比例しているようです。（リュカレーマーテストの実行速度がO(N^2)らしいのでその関係かな？参考：http://intmain.hatenablog.com/entry/2016/12/29/023549）
最終的には2147483647ビットの計算をしたいので、２１億×２１億×5.68×10^-8≒2.5千億秒（8000年？）かかることになります。
・・・・・・これは厳しい。
1億桁の素数を見つけて早期退職したいのに、その前に定年が来てしまう……。
リュカ・レーマーテストを高速化する必要がありますね。
剰余算をビット演算にすることで高速化可能らしいですが、どの程度早くなるのでしょうか？（そもそもPythonの剰余算がそこそこ最適化されている可能性があるし）
GPUも使えたら使っていきたいですが、……並列処理ってある？
あと、p=2147483647を入力したところ、メモリエラーで弾かれました。
２１億ビットのメモリの扱いをどうするかも課題ですね。
リュカ・レーマーテストを超える高速な素数判定法が必要かもしれません。
ええ！リュカ・レーマーテストより早く素数を判定！？
できらぁ！リュカ・レーマーテストより早く素数を判定するって言ってんだよ！
え！リュカ・レーマーテストより早く素数を判定！？
次回は気が向いたらビット演算しようかなと思います。だいぶ先になると思います。
つづけ
（P.S.昨夜から33番目のメルセンヌ素数（p=859,433）を探しに行ったリュカ・レーマーテストが帰ってきてません。誰かなんとかしてください。）
そーめんブログ 