binary exponentiation

任意の数の累乗を計算する時には、for文で累乗する回数だけ数を掛け合わせる、というのは小学生でも思いつく。だが、累乗する回数が大きくなったとき、例えば1億乗とかやられたときには極端に遅くなるのは明らかだ。

二進累乗法というやり方がある。これは2の累乗に乗数を展開することで、掛ける回数をビット数＋数回に抑えるという考え方だ。累乗する数を1ビットシフトして掛けることで、x^2, x^4, x^8, x^16 ... といった具合で累乗する回数を2の累乗倍に増やしていくことで、累乗する回数を減らすことができる。

累乗する回数を減らすことは、累乗する対象の値が double だった場合に誤差を減らす効果をもたらす。
.... って、言葉で言ってもわけわかんないすよね(´ー｀; )



[ Update September 11th 2012 06:32 JST by m ]

べき乗のアルゴリズムのうち、上位桁から計算する方法 を上記はコードにしたものだ。これの計算量は 最大でも 2 * logN (N は累乗する回数) なので、O(logN) となる。