素数判定を1.5倍速くする話

あと対32bit/64bit限定高速素数判定頑張った http://t.co/nTP8RI7Uhh てのも読んだ。巧いwitnessとればそれぞれミラーラビン3発/7発で確実に判定できることが知られているわけだけど、最初にハッシュで擬素数を散らすことでそれぞれ1発/3発で倒す

— kinaba (@kinaba) 2015, 1月 27

このツイートを見てこの論文の存在を知り、どのくらい速くなるのか疑問に思ったので性能評価をしてみました。

やったこと

32bit符号なし整数の高速な素数判定方法の実装及び既存のアルゴリズムとの性能比較。

環境

学科で渡されたノートパソコン。

• CPU: Intel® Core™ i5 CPU M 460 @ 2.53GHz × 4 (64bit)
• 言語: C++
• コンパイラ: g++
• コンパイルオプション: -O2 -Wall
• ソースコード: https://github.com/koba-e964/misc-algo/blob/4dc54f6ec0ada988671c6b19b041dd5444ee993b/prime/Forisek.cpp

結果

$ g++ -O2 -Wall Forisek.cpp -o Forisek
$ time ./Forisek 1
prime count: 14630842

real 0m30.210s
user 0m30.182s
sys 0m0.000s
$ time ./Forisek 2
prime count: 14630842

real 0m45.133s
user 0m45.035s
sys 0m0.012s

上が論文の手法、下が2,7,61の3種類の底によるMiller-Rabin法です。
およそ1.5倍の高速化となりました。

考察

どちらの手法でも高速化のために小さな約数があるかの判定を行っているので、単純に3倍にならなかったものと思われます。

これから

64bit符号なし整数の素数判定についてはまだ読んでいないので、これから取り組んでみます。
結局学生の手抜きレポートみたいな出来になってしまった…(>_<)

参考

ミラー-ラビン素数判定法 - Wikipedia Miller-Rabin法自体の詳細はここが参考になります。
Miller-Rabin SPRP bases records Miller-Rabin法の底の選び方などの参考になります。