読者です 読者をやめる 読者になる 読者になる

SuperCon2010予選通過報告とソース

Programming Algorithm

去年優勝しました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なりが使えたら面白そうだし話題性もあるしいいと思う。