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

繰り返し２乗法とは

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

例

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

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

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

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

具体的に考える。

xⁿ における n = 10を考える。

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