マツシタのお勉強

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

繰り返し2乗法とは

繰り返し2乗法とは、べき乗計算する際に通常なら計算量O(N)かかる所をビット操作を用いてO(logN)にする手法である。

3^10を計算することを考える。

通常なら以下のようにループを10回繰り返す。

よってx^nの計算量はO(n)となる。

これを以下のようにすることで、O(logN)まで小さくする。

具体的に考える。

xn における n = 10を考える。

この性質によって2進数の見ている桁をmとするとm & 1 == 1(フラグが立っている)の時、 2m乗した数を掛けた数の積が求めたいものになる。