ビット演算使ってリュカレーマーテストを高速化したお話
ビット演算にした部分
リュカレーマーテストでコストがかかる部分は主に2つ、二乗の演算と剰余算です。ちなみにどちらが痛いかというと剰余算です。(今回わかった)
リュカレーマーテストに出てくる剰余算は割る数が限定されている(判定対象のメルセンヌ数)なのでbit演算に落とし込めそうだと思いたち、実装して今に至ります。
方法
※判定対象pを2^i-1とします。で割る数をnとします。ここではnをpで割ったあまりを求める操作を考えます。
1、nをpでマスクして下位iビットを得ます。
2、nをiビット右シフトして上位ビットを得ます。
3、1と2の結果を足してnに入れときます。
4、1~3をn<=pになるまで繰り返します。
5、n=pならn=0にします。
証明(というより詳しく言っただけ)
1はnのp以下の部分を求めるところです。pを2^iと近似しているため5のような処理が最後に入ってきます。
2について。1のpを2^iと近似するものによれば、nのp以上の部分には(n>>p)個のpがあるわけです。真値は2^i-1なのでこれ一つ一つにあまりが1ずつ発生していることになります。これを全部足したいのでnをi桁ビットシフトしてます。
3について足します。
4について。1と2を1回ずつ実行しただけでは64とかの数では答えが8とかになります。これを防ぐために複数回実行しています。(なので割る数とオペランドのbit数に大きな差がある場合は遅くなる)
5について。このままだと割る数にpの倍数を代入された時にpが返ってしまいます。それを防ぐためです。
結果
30番目、2^132049-1を判定。上が今回、下が従来
5倍弱ぐらいの速度になってますね。今回のもので、割り算単品でかかっているコストがどの程度なのか分かりませんがだいぶ速くなっているはずだと信じています。
(実行環境i7 4770K single thread, linuxmint18 64bit, g++, gmp)
終わりに
リュカレーマーテストの最大の問題である、実行速度がO(N^2)という点は変わっていませんが(変わったらマジで大事件だけど)、比例定数を落とすことには成功していると思います。二乗に関してはgmpを使っての実装なのでこれ以上にはならないでしょう。(GPU使うなら話は別ですが)
P.S.年明けにGTX1060 6GB買います