べき乗の計算は、ふつう次のように行う。
例えば、aの13乗を計算するとき、
13を2進数で表すと1101、
まず2乗して、
a2 = a * a
2進表示の左から2番目が1なのでaをかけて、
a3 = a2 * a
2乗して、
a6 = a3 * a3
2進表示の左から3番目が0なのでそのまま。
2乗して、
a12 = a6 * a6
2進表示の左から4番目が1なのでaをかけて、
a13 = a12 * a
と、5回の乗算が必要である。
Wikipediaにも同様のアルゴリズムが載っている。
http://ja.wikipedia.org/wiki/%E5%86%AA%E4%B9%97
一般に、2進数で表示して、最上位桁を無視して、
各桁に1をたして、各桁をたし合わせると、
必要な乗算の回数が出てくる。
1101 -> 101 -> 2+1+2 -> 5回
しかし、これは最も効率のよいべき乗の計算法とはいえない。
例えば、27乗は、このアルゴリズムなら、
a2 = a * a
a3 = a2 * a
a6 = a3 * a3
a12 = a6 * a6
a13 = a12 * a
a26 = a13 * a13
a26 = a26 * a
と、7回の乗算が必要である。
しかし、次のようにすると6回で済む。
a2 = a * a
a3 = a2 * a
a6 = a3 * a3
a9 = a6 * a3
a18 = a9 * a9
a27 = a18 * a9
このように、本当に乗算が少ない計算法を見つけるにはどうしたらよいだろうか。
