明けまして、素数野郎2
あけましておめでとうございます。新年の挨拶やら去年のことなんかを先に書くべきかもしれませんが、Prime checker(http://www.spoj.pl/problems/PRIC/)が気になって仕方ないのでとりあえずその話だけ。あれから頑張ってチューニングしたら、21,000,000個までイケました。もうちょっとでBest10。
アルゴリズムはそれほど凝ったものではなくて小さな素数で篩いにかけた後ミラー・ラビンの素数判定をやっただけです。もちろん、誤って判定してしまう値のリストは埋め込んでありますが。剰余計算を減らしただけでかなりのスピードアップになるようです。ちょっと手詰まり感が出てきたので計算方法を調べてみたら、モンゴメリ乗算とかいうやつがあるみたいなのですがよくわかりません。なんか前処理をやっとくと乗除回数が少なくて済むんでしょうかね。
インラインアセンブリでぐっちゃぐちゃなので、そろそろ新しいアルゴリズムで書き直さないとダメっぽいです。数列自体は規則的に変化するわけだから、素数自体の判定はミラー・ラビンのままだとしても、明らかに素数じゃない数というのは何か上手い判定方法があるような気がします。2147483647を超える場合とそうでない場合がややこしい感じがするけど、逆にそれが利用できるんじゃないかと思ったり思わなかったり…
何か良い方法ないかなぁ。
