知識メモ
知識メモ
a の累乗 a^N を次の方法で速く計算できる。
N を二進法で
N = 2^{s_1} + 2^{s_2} + ... + 2^{s_k}, \ \ 0 \leq s_1 < s_2 < ... < s_k
と展開する。すると
a^N = a^{2^{s_1} + 2^{s_2} + ... + 2^{s_k}} = a^{2^{s_1}} a^{2^{s_2}} ... a^{2^{s_k}}
であり、各 a^{2^{s_i}} は
a \rightarrow a^2 \rightarrow (a^2)^2 = a^{2^2} \rightarrow (a^{2^2})^2 = a^{2^3} \rightarrow ...
と、前の数の平方を順次取っていくことで求められる。

普通に累乗計算したときのオーダーは O(N) であるが、この方法なら O(log_2 N) で計算できる。


（例）
3^11の計算
11 = 1 + 2 + 8 = 2^0 + 2^1 + 2^3
なので、
3^1 = 3
3^2 = 9
3^4 = 9^2 = 81
3^8 = 81^2 = 6561
を用いれば
3^11
= 3^{1 + 2 + 8}
= 3^1 × 3^2 × 3^8
= 3 × 9 × 6561
= 177147

タグ：

情報理論
「高速累乗計算法」をウィキ内検索
最終更新：2012年08月31日 03:32