差分
定数倍高速化
,編集の要約なし
==概要==[[競技プログラミング]]においてはほとんどの場合意味がないが、たまに定数倍高速化で無理矢理通せる場合、においてはほとんどの場合意味がないが、たまに定数倍高速化で無理矢理通せる場合、[[想定解]]のアルゴリズムだけど自分のの[[アルゴリズム]]だけど自分の[[実装]]が悪いので定数倍高速化しないと通らない場合など、定数倍高速化が役に立つ場面がある。が悪いので定数倍高速化しないと通らない場合など、定数倍高速化が役に立つ場面がある。
==例==
</source>
このコードは、a,bがULLONG_MAX/2以下、cがULLONG_MAX/2+1以下のとき、
(a*b) mod cを[[オーバーフロー]]しないように気をつけながら求めるプログラムである。しないように気をつけながら求める[[プログラム]]である。
しかし、よく考えると、最初に与えられるaがc未満のとき、常にresult+a<2*c,(a<<1)<2*cが成り立つことがわかる。
<source lang="c">
/* suppose that a<c */
===なるべく再帰を使わない===
[[再帰]]を使ったプログラムは、再帰を使わない処理に比べて、を使った[[プログラム]]は、再帰を使わない処理に比べて、
[[関数]]の呼び出しによる[[スタック]]の確保・復帰処理が入るため低速になることが多い。
}
</source>
===OpenMPを使う===
実行中の[[CPU]]使用率を上げる代わりに実行時間を短くすることができる。
詳しくは、[[OpenMP]]のページを見ていただきたい。