SuperCon2010予選通過報告とソース
去年優勝しましたZATORIKUは今年もSuperCon楽しませてもらいます。二連覇しますよ。
期末なのでこれ書いたら寝ます。
解法概要
- mが奇数のとき0
- そうでない場合、[ [0,1],[1,1] ]^nと[ [1,2],[1,3] ]^(m/2)のしかるべき位置の積
- 行列累乗はバイナリ法を利用
- O(l(log n+log m)) ただしl=600,000
最適化
- 2x2の行列の累乗は2変数で表現できる、など、変数の削減→nについては内部ループ1回につき3回、mについては内部ループ1回につき4回の剰余演算(分岐なし)で可能
- 変数削減したうえで、使う変数だけをまとめてブロックにすると、最適化がうまく効くのか、微妙に速くなったりした
- nについては32乗、mについては16乗まではintの範囲に収まるのでprecalculate
- すこし速くなったっぽい
- ループのアンローリング
- これで分岐がかなり減る
効果があったかはわからない
なお、以下の最適化は結局使わなかった
- kの奇数因子についてMontgomery乗算の適用、kの2^n因子についてはビット演算。最後に結果を結合
- 分岐が多くなるからだめだったのかも。または、Montgomeryのために必要なprecalculateに時間がかかったのかも
ところで
本選でCUDAなりOpenCLなりが使えたら面白そうだし話題性もあるしいいと思う。
