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

べき乗

繰り返し2乗法を使ったべき乗計算

繰り返し2乗法とは 繰り返し2乗法とは、べき乗計算する際に通常なら計算量O(N)かかる所をビット操作を用いてO(logN)にする手法である。 例 ば3^10を計算することを考える。 通常なら以下のようにループを10回繰り返す。 よってx^nの計算量はO(n)となる。 …