続素数判定

ついに戦いの舞台は4秒台へ。

もうアルゴリズムとソースを公開して終わりにしようと思っていたのだけど、そうは問屋がおろさなかった。いい加減、私も負けず嫌いなんだと思いますよ。前回の段階ではアルゴリズムを適当に実装して最適化の工夫は全くしていない状態だったのですが、まさかここまで速くなるものだとはなあ。

手元のCore2 1Ghzで1.4秒、Core2 2.4Ghzで0.6秒ぐらいです。向こうの環境は良く分からないのですが、たぶんこちらよりも2次キャッシュがだいぶ少ないのと、GCCが定数割り算の掛け算化をやっているのかやっていないのかわからないけどとりあえず定数除算が手元よりも大幅に遅いのと、そもそも掛け算のレイテンシも大きいような感じで、こっちで速くなってもあっちで速くならずのような不毛な試行錯誤を繰り返しておりました。まあそれにしても、結局有意に速くなるのは演算回数を真に削減したときぐらいですが。

アルゴリズムは、まだ下げ止まっていないようなので、今公開すると興をそぐと考えて、もう少し保留しておきます。でもたぶん同じような方法だとは思いますが。