冪乗

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

冪乗(べきじょう)、または累乗(るいじょう、: exponentiation) は、ある一つの数同士を繰り返し掛け合わせるという操作のこと、あるいはそれによって得られる数のことである。単に(べき)ともいう。

「冪」の文字はもともと「覆う、覆うもの」という意味の漢字である。江戸時代和算家は略字として「巾」を用いた[1]常用漢字当用漢字に含まれなかったことから1950年代以降、出版物などでは仮名書きまたは「累乗」への書き換えが進められた。結果として初等数学の教科書ではもっぱら「累乗」が用いられ、「冪」や「冪乗」という用語は排除されたが、一方で「降べき順」「昇べき順」というような用語の一部としては残ったままになっている。

定義[編集]

実数全体の集合やなど積の定義された集合 X 、その集合 Xの元 x 、および、自然数 n があるとき、 xn 個掛け合わせることによってできる、X の新たな元 xn

x^n = \underbrace{x \times \cdots \times x}_{n\ \text{times}},

と定義する。また、これを“ xn-乗”と呼ぶ[2]。冪乗 xn において、x(てい、: base基数)と呼び、n冪数冪指数または単に指数(しすう、 : exponent) と呼ぶ[3]。また、底 x を固定し、冪指数 n を任意の自然数にわたって動かすときに得られる数を総称して、x を底とする冪乗、または単に x の冪と呼ぶ。また、必ずしも冪指数とは限らない添字 n をその基準となる文字 x の右肩に乗せる添字記法を指数表記・冪記法などとよぶ場合もある。

冪乗は

  1. x1 = x,
  2. xn+1 = xn × x   (n ≥ 1)

のように帰納的に定めることも可能である。冪乗を集合から集合への写像として説明すれば、自然数全体の集合N があるとき、その冪乗による集合 X写像

N × XX; (n, x) → xn

であると定義される。このとき、例えば、指数 n を固定して、x を変数とする写像 XX; xxn を考えることができる。また、底 x を固定して N から X への写像 nxn も考えられる[4]。このような関数を総称して(X 上の)冪写像あるいは冪関数と呼ぶ。

x の 2乗、3乗は特に、それぞれ x平方 (へいほう、 : square)、立方 (りっぽう、 : cube) と呼ぶ。この呼び名はそれぞれ、「正方形」、「立方体」の「方」、「立方」と同じものである。2-乗を自乗ということもある。

指数の拡張と指数法則[編集]

正数と0と負数[編集]

正負を伴う累乗では、整数 x に対して、指数が正の整数 n であれば xn となり、指数が 0 であれば 1 となり、指数が負の整数 −n であれば 1 / xn となる。指数が 0 だと 1 になる要因は、分子分母が同値になるからである。

例えば、2の累乗数を例に取ると:

というように倍増されたり分割されたりする。

累乗根[編集]

同様に、自然数 m に対し、xm 乗根すなわち m 乗して x になるような数 y がただ一つあるならば、その yx1/m とし、自然数または整数 n に対し

xn/m = (x1/m)n

と定めることによって、x を底とする冪乗の指数を有理数の範囲まで拡張することができる。 このとき、指数法則と呼ばれる以下の関係式が成り立つ。

  • xr+s = xr × xs
  • xr×s = (xr)s

ここで、rs は、冪乗が定義できる範囲の有理数である。つまり、x が逆元をもたないなら自然数、逆元はもつが冪根をもたないなら整数、m 乗根をもつが逆元をもたないならば m を分母とする正の有理数、逆元も m 乗根ももつならば m を分母とする有理数である。また、xy が積 × について可換ならば

  • (x × y)r = xr × yr

が各項がきちんと定義されるような有理数 r に対して成り立つ。これも指数法則と呼ばれることがある。

なお、考えている集合が、単位元をもつ・積が可換な構造をもつならば、その和 + について、指数が自然数 n であるような冪

(x + y)n

二項定理に従う。

指数関数[編集]

上で述べたことを x が実数の範囲で考えてみると、x が 0 でないならば 1/xx の逆元であるから、

xn = (1/x)n = 1/xn

と一意的に定めることができる。また、x が正の数であれば任意の自然数 m に対する正の m 乗根 mx がただ一つだけ存在するから、任意の有理数 n/m に対し

x^{n/m} = (\sqrt[m]{x})^n = \sqrt[m]{x^n}

と定めても齟齬を生じない。

以上のことから、a が正の実数のとき、a を底とする冪乗の指数が有理数の範囲全体 Q で定義されたことになる。このとき、a の冪乗はその指数に関して単調性をもつので、実数全体の集合 R における有理数の稠密性から、これは R 上で定義された連続関数に一意的に拡張される。これを a を底とする指数関数と呼ぶ。

0の0乗に関して[編集]

しばしば議論になるところだが、0の0乗は通常定義されない。

効率的な演算法[編集]

コンピュータ上で冪乗演算を行なう効率的な演算方法としてバイナリ法二進数法)とも呼ばれる演算方法を示す。

RSA暗号確率的素数判定法であるフェルマーテストなどによって、指数として巨大な自然数を扱うことが多くなった。この方法を使うと、指数となる自然数がいかに巨大であっても高々そのビット数の2倍の回数の乗算で算出することが可能になり、繰り返し掛けるよりも大幅に効率がよくなる。特にRSA暗号やフェルマーテストなどにおいて各演算後に必要となる剰余演算(一般に最も計算時間がかかる)の回数を減らす効果がある。

一般に、コンピュータにとって標準的な(32bitsコンピュータならば約4億までの)自然数や浮動小数点数を扱う場合は下位桁から計算する方式を、前述のような巨大な自然数を扱う場合には上位桁から計算する方式を用いると効率が良い。

下位桁から計算する方式[編集]

バイナリ法では、次の性質を利用する。

(ax)2 = a2x

例えば (a8)2 = a16 である。したがって、a(すなわち a1)から始めて2乗を繰り返すとこうなる。

a1a2a4a8a16a32 → …

これらの数のうち、適切なものを選んで掛け合わせれば、任意の累乗を速く(すなわち少ない乗算回数で)計算することができる[5]。例えば a43 は、上で示した指数法則によって、

a43 = a32+8+2+1 = a32×a8×a2×a1

として計算することができる(乗算回数は 8 回で済むので、a を 42 回繰り返し掛け合わせるのに比べて効率がよい)。

(十進表記):   a1 a2 a4 a8 a16 a32
2乗の繰返し(二進表記):   a1 a10 a100 a1000 a10000 a100000
       
累乗の計算(二進表記):   a1 a11 →→ a1011 →→→ a101011
    a43

コンピュータアルゴリズムとして書くとこうなる。下位桁から順に扱うことから、順に2で割ると同時にその余りを求め(実際にはシフト演算を用い)ながら演算を行うことで二進表記を省略し、効率を高める。

  1. 指数を n とし、2乗していく値 p := a 、結果値 v := 1 とする。
  2. n が 0 なら、v を出力して終了する。
  3. n の最下位桁が 1 なら、v := v * p とする。
  4. n := [n/2] とし(端数切り捨て)、 p := p * p として、2. に戻る。

この方式はaが浮動小数点数である場合や、最終結果がレジスタに収まることがわかっている場合に効率が良い。また乗算にモンゴメリ乗算などを用いて冪剰余を計算する場合も、この方式で充分な効率が得られる。

上位桁から計算する方式[編集]

上の方式と同様に、次の性質を使う。

a^{2x} = \left( a^x \right)^2

これに性質 a^{x+1} = a^x \cdot a を組み合わせると、次の変形ができる。

a^{2x+1} = \left( a^x \right)^2 \cdot a

これら二つの式を適宜使い分けることによって、指数を順次約1/2にしていくことができる。例えばa^{43}は、上で示した指数法則によって、

a^{43} = a^{21 \cdot 2 +1} = \left( a^{21} \right) ^2 \cdot a

である。そしてa^{21}も同様に、

a^{21} = a^{10 \cdot 2 +1} = \left( a^{10} \right) ^2 \cdot a

である。a^{10}はこうなる。

a^{10} = a^{5 \cdot 2} = \left( a^{5} \right) ^2

以下同様に、

a^{5} = a^{2 \cdot 2 +1} = \left( a^{2} \right) ^2 \cdot a
a^{2} = a^{1 \cdot 2 } = \left( a^{1} \right) ^2
a^{1} = a

となる。これを逆にたどり、

a^{43} = \left( \left( \left( \left( \left( a \right) ^2 \right) ^2 \cdot a \right) ^2 \right) ^2 \cdot a \right) ^2 \cdot a

として算出する。

この各演算において、2乗した後にaを乗算するのか否かの判定は、ちょうど指数nを二進表記したときの各ビットが1であるか否かと一致する。

コンピュータのアルゴリズムとして書くとこうなる。

  1. 指数 n を二進表記したものを n とし、n の最下位桁を n[0]、最上位桁を n[m]、最下位から数えて k 桁目を n[k] と表記する。
  2. 結果値 v := 1 とし、
  3. k := m とする(最上位)。
  4. v := v * v
  5. n[k] が 1 ならば v := v * a とする。
  6. k := k - 1
  7. k ≧ 0 なら 4. に戻る。

この方式では、5.における乗数が常にaなので、下位桁から計算する方式に比べて乗数の桁数が小さくてすみ、計算時間がかからない。このことは特に、レジスタに入りきらないような巨大な自然数を扱う場合に顕著となる。ただし(RSA暗号で冪算する時のように)冪乗の剰余を計算する場合であって法の大きさがaと同程度ならば、この効果はない。

また5.における乗数が常にaなので、あらかじめaが定数(2や10など、あるいはディフィー・ヘルマン鍵共有の生成元gなど)であることがわかっている場合には5.の乗算そのものを最適化をすることができる。

巨大な自然数の汎用的な冪算ルーチン(aが小さい可能性が高い)や、aが小さかったり定数であることがわかっている場合、冪乗の剰余を計算する場合であってモンゴメリー演算を用いず別途剰余を計算する場合、数を保持するコストが高い場合など、指数を二進表記するコスト以上の効率が得られる場合に選択される。

脚注[編集]

  1. ^ 王青翔 (1999), 「算木」を超えた男, 東京: 東洋書店, ISBN 4-88595-226-3 
  2. ^ アーベル群など加法的に記される演算を持つ代数系における n-乗 xn の対応物は n-倍 nx である。
  3. ^ 単に「指数」と呼ぶ場合、"exponent" に限らず、(数学に限っても)種々の index を意味する場合も多く、文脈に注意を要する(たとえば部分群の指数)。また、(必ずしも冪指数のことでない)"exponent" の訳として冪数が用いられることもある(たとえば有限群の冪数)。
  4. ^ これは後述するような指数の拡張に伴い定義域を拡張できる場合がある。
  5. ^ 奥村晴彦 『C言語による最新アルゴリズム事典』 技術評論社1991年、304頁。ISBN 4-87408-414-1

関連項目[編集]