冪乗
著者:梅谷 武
語句:ピンガラ,クヌース,チャンドハスートラ,冪乗,指数
冪乗の記法と算法。
作成:2006-04-14
更新:2013-06-16
 数式表記において同じ数を何回も掛けるときに冪乗べきじょう, power, exponentialの記号を使うと便利です。nを任意の自然数としたとき、
an
a × ⋯ × a (n個の積)
a0
1
a-n
1
an
, a≠0
と定義します。これにより、任意の整数kについてakが定義できますが、このkのことを指数しすう, exponentといいます。

命題1.5.2 指数法則

aを有理数、m,nを整数とすると次が成り立つ。
(1) am an = am+n
(2) (am)n = amn
(3) (ab)n = an bn

証明

 演習とする。■

例題1.5.4

216を計算せよ。
 これを計算するときに2を16回かける人はいないでしょう。2×2 = 4(=22)4×4 = 16(=24)16×16 = 256(=28)256×256 = 65536(=216)とすると4回の乗算で計算できます。
 冪乗を効率よく計算するという問題はかなり古くから考えられていました。紀元前200年頃のインドのピンガラPingala, BC200頃の『チャンドハスートラChandah-sûtra』に2nの指数nを2進表記することで効率的に冪乗を計算する算法が書かれています。9世紀以降にそれが任意の数aの冪乗anを計算する算法に一般化されました。クヌースKnuth, Donald Ervin, 1938-により整理された形でその算法を紹介します。
 まず、簡単な場合をいくつか見てみましょう。
a4
=
a22 =a4
a5
=
a1+22 =a a4
a6
=
a2+22 =a2 a4
a7
=
a1+2+22 =a a2 a4
指数が奇数の場合にはaで割ることで偶数にし、a2aと置き直して指数が半分の場合に帰着させることができることがわかります。この算法はかならずしも乗算回数を最小にするものではありませんが、単純で簡単に実装することができますので便利です。これを算法としてまとめ、プログラミング例を示します。

算法1.5.8 繰り返し二乗法

 可換環の元aと正の整数nが与えられたときにanを計算する。
Step 1. aとnを入力する。
Step 2. answer = 1
Step 3. nが0ならば終了する。
Step 4. nが奇数ならばanswer = answer * aとする。
Step 5. a = a * a; n = n / 2とし、Step 3.へ。

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によって計算できます。
[1] D.E.Knuth(中川圭介訳), 準数値算法―算術演算, サイエンス社, 1986
img
 
 
[2] D.E.Knuth(有沢誠他訳), The Art of Computer Programming (2) 日本語版 Seminumerical algorithms, アスキー, 2004
img
 
 
人  物
ピンガラ Pingala, BC200頃
ヴェーダ文献の韻律学者。ヴェーダ文献とは紀元前2000年頃から北インドに侵入してきたアーリア人が作り出した一群の宗教的文献。
クヌース Knuth, Donald Ervin, 1938-
アメリカの数学者、計算科学者。"The Art of Computer Programming"の著者。
 
物  品
チャンドハスートラ Chandah-sûtra
ピンガラが著した韻律学書。第4章でその内容の一部が紹介される。
 
数  学
冪乗 べきじょう, power, exponential
指数 しすう, exponent
 
Published by SANENSYA Co.,Ltd.