数式表記において同じ数を何回も掛けるときに冪乗べきじょう, power, exponentialの記号を使うと便利です。nを任意の自然数としたとき、 と定義します。これにより、任意の整数kについてa^kが定義できますが、このkのことを指数しすう, exponentといいます。

 これを計算するときに2を16回かける人はいないでしょう。2×2 = 4(=2²)、4×4 = 16(=2⁴)、16×16 = 256(=2⁸)、256×256 = 65536(=2¹⁶)とすると4回の乗算で計算できます。

 冪乗を効率よく計算するという問題はかなり古くから考えられていました。紀元前200年頃のインドのピンガラPingala, BC200頃の『チャンドハスートラChandah-sûtra』に2ⁿの指数nを2進表記することで効率的に冪乗を計算する算法が書かれています。9世紀以降にそれが任意の数aの冪乗aⁿを計算する算法に一般化されました。クヌースKnuth, Donald Ervin, 1938-により整理された形でその算法を紹介します。

 まず、簡単な場合をいくつか見てみましょう。 指数が奇数の場合にはaで割ることで偶数にし、a²をaと置き直して指数が半分の場合に帰着させることができることがわかります。この算法はかならずしも乗算回数を最小にするものではありませんが、単純で簡単に実装することができますので便利です。これを算法としてまとめ、プログラミング例を示します。

sample1.5.3.py

def power( a, n ):
  answer = 1
  while n != 0:
    if n % 2 == 1:
      answer *= a
    a *= a
    n /= 2
  return answer
 
a = 2
n = 16
p = power( a, n )
print 'power( %d, %d ) = %d' % ( a, n, p )

sample1.5.3.pyの実行結果

mul count = 6
power( 2, 16 ) = 65536

sample1.5.3.rb

def power(a, n)
  answer = 1; count = 0
  while n != 0
    if n % 2 == 1
      answer *= a; count += 1
    end
    a *= a; count += 1
    n /= 2
  end
  printf "mul count = %d\n", count
  return answer
end
 
a = 2
n = 16
p = power(a, n)
printf "power(%d, %d) = %d\n", a, n, p

sample1.5.3.rbの実行結果

mul count = 6
power(2, 16) = 65536

 乗算回数をさらに減らす算法についてはクヌースの本を参照してください。なお、上のプログラムにおいて整数の冪乗を計算していますが、Python/Rubyにおいては整数の冪乗が組み込まれており、a**nによって計算できます。

参考文献