冪乗

出典: フリー百科事典『ウィキペディア（Wikipedia）』
2014年4月28日 (月) 18:46時点における42.125.160.141 (トーク)による版
(差分) ← 古い版 | 最新版 (差分) | 新しい版 → (差分)
移動先: 案内、 検索

冪乗（べきじょう、テンプレート:Lang-en-short）、または累乗（るいじょう、テンプレート:Lang-en-short) は、ある一つの数同士を繰り返し掛け合わせるという操作のこと、あるいはそれによって得られる数のことである。

誤用としての「べき乗」と語の歴史

「冪乗（べきじょう）」という語は本来なく、誤用が定着したものである。 「冪」の文字はもともと「覆う、覆うもの」という意味の漢字であり、江戸時代の和算家は略字として「巾」を用いていた[1]。ところがどちらも常用漢字・当用漢字に含まれなかったことから1950年代以降、出版物などでは仮名書きまたは「累乗」への書き換えが進められ、結果として初等数学の教科書ではもっぱら「累乗」が用いられた。

この際、n乗を取る操作の伝統的名称である「n-乗冪」[2] と「累乗」が混同され、「冪乗（べきじょう）」という語を生じた。 一方で、「冪根」「冪剰余」「冪集合」などの高等学校以下で扱われない概念に対しては、「べき乗根」などといった表現は生じていない。

定義

実数（など積 <math>\times</math> の定義された群 ）において、元 x 、および、自然数 n に対して xn を

<math>x^n = \underbrace{x \times \cdots \times x}_{n\ \text{times}},</math>

で定義する。（厳密には帰納法による。） 上付きのnが書けない場合などには、x^nという表記を用いることが多い。 これを x の n-乗あるいは xのn-乗冪と呼び、nを問題にしないときはxの累乗やxの冪と言う。

また、これら操作を「xのn乗（etc）を取る」などと称し、特にnを固定してxを入力とする関数と見るときは、冪関数という。 x の 2乗、3乗は特に、それぞれ x の平方 (へいほう、 テンプレート:Lang-en-short)、立方 (りっぽう、 テンプレート:Lang-en-short) という呼ばれ、2-乗を特に自乗という場合もある。

冪 xn において、x を底（てい、テンプレート:Lang-en-short、 基数）と呼び、n を冪数、冪指数または単に指数（しすう、 テンプレート:Lang-en-short) と呼ぶ[3]。また、必ずしも冪指数とは限らない添字 n をその基準となる文字 x の右肩に乗せる添字記法を指数表記・冪記法などとよぶ場合もある。

厳密には、xのn-乗冪は帰納法を用いて

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

と定義される。

指数の拡張と指数法則

以下では、底xの範囲を実数に限らず、一般的な群を念頭に議論する。 指数は自然数上で定義されていたが、実数上や一般的な順序群上に拡張することができる。

指数の整数への拡張

帰納的定義を見れば以下のように拡張するのが自然である。

有理数の範囲で2の累乗数を例に取ると：

ただし、底が0の場合は「0で割れない」などの理由から定義しないのが普通である。 テンプレート:Main

累乗根

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

xn/m = (x1/m)n

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

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

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

正の実数の実数べき

x が正の実数であれば、上で制限されていた指数への条件は外れる。 なぜなら、正数であれば任意の自然数 m に対する正の m 乗根 m√x がただ一つだけ存在するから、正の有理数 n/m に対し

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

と定めることができるし、さらにxが0でなければ逆元が存在するので、指数は有理数全体まで拡張される。

さて、x (>0) の冪はその指数に関して単調性をもつので、実数全体における有理数の稠密性から、これは実数上で定義された連続関数に一意的に拡張される。これを x を底とする指数関数と呼ぶ。

効率的な演算法

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

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

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

下位桁から計算する方式

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

(ax)2 = a2x

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

a1 → a2 → a4 → a8 → a16 → a32 → …

これらの数のうち、適切なものを選んで掛け合わせれば、任意の累乗を速く（すなわち少ない乗算回数で）計算することができる[4]。例えば 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. 指数を <math>n</math> とし、2乗していく値 p := a 、結果値 v := 1 とする。
  2. n が 0 なら、v を出力して終了する。
  3. n の最下位桁が 1 なら、v := v * p とする。
  4. n := [n/2] とし（端数切り捨て）、 p := p * p として、2. に戻る。

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

上位桁から計算する方式

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

<math>a^{2x} = \left( a^x \right)^2</math>

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

<math>a^{2x+1} = \left( a^x \right)^2 \cdot a</math>

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

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

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

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

である。<math>a^{10}</math>はこうなる。

<math>a^{10} = a^{5 \cdot 2} = \left( a^{5} \right) ^2</math>

以下同様に、

<math>a^{5} = a^{2 \cdot 2 +1} = \left( a^{2} \right) ^2 \cdot a</math>
<math>a^{2} = a^{1 \cdot 2 } = \left( a^{1} \right) ^2</math>
<math>a^{1} = a</math>

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

<math>a^{43} = \left( \left( \left( \left( \left( a \right) ^2 \right) ^2 \cdot a \right) ^2 \right) ^2 \cdot a \right) ^2 \cdot a </math>

として算出する。

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

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

  1. 指数 <math>n</math> を二進表記したものを 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が小さかったり定数であることがわかっている場合、冪乗の剰余を計算する場合であってモンゴメリー演算を用いず別途剰余を計算する場合、数を保持するコストが高い場合など、指数を二進表記するコスト以上の効率が得られる場合に選択される。

脚注

テンプレート:Reflist

関連項目

テンプレート:二項演算テンプレート:Link GA

  1. ↑ テンプレート:Citation
  2. ↑ {関孝和}
  3. ↑ 単に「指数」と呼ぶ場合、"exponent" に限らず、（数学に限っても）種々の index を意味する場合も多く、文脈に注意を要する（たとえば部分群の指数）。また、（必ずしも冪指数のことでない）"exponent" の訳として冪数が用いられることもある（たとえば有限群の冪数）。
  4. ↑ テンプレート:Cite book
「http://wikippe.e-do-match.com/index.php?title=冪乗&oldid=9597」から取得