冪乗のソースを表示

'''冪乗'''（べきじょう、{{lang-en-short|''power''}}）、または'''累乗'''（るいじょう、{{lang-en-short|''exponentiation''}}) は、ある一つの数同士を繰り返し掛け合わせるという操作のこと、あるいはそれによって得られる数のことである。

== 誤用としての「べき乗」と語の歴史 ==
「冪乗（べきじょう）」という語は本来なく、誤用が定着したものである。
「冪」の文字はもともと「覆う、覆うもの」という意味の漢字であり、[[江戸時代]]の[[和算]]家は略字として「巾」を用いていた<ref>{{Citation|title=「算木」を超えた男|last=王青翔|isbn=4-88595-226-3|publisher=東洋書店|place=東京|year=1999}}</ref>。ところがどちらも[[常用漢字]]・[[当用漢字]]に含まれなかったことから[[1950年代]]以降、出版物などでは[[仮名 (文字)|仮名]]書きまたは「累乗」への書き換えが進められ、結果として[[算数|初等数学]]の教科書ではもっぱら「累乗」が用いられた。

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

== 定義 ==
[[実数]]（など積 <math>\times</math> の定義された[[群]] ）において、元 ''x'' 、および、[[自然数]] ''n'' に対して
''x''<sup>''n''</sup> を 
:<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|''square''}})、'''立方''' (りっぽう、 {{lang-en-short|''cube''}}) という呼ばれ、2-乗を特に'''自乗'''という場合もある。

冪 ''x''<sup>''n''</sup> において、''x'' を'''底'''（てい、{{lang-en-short|''base''}}、 '''基数'''）と呼び、''n'' を'''冪数'''、'''冪指数'''または単に'''指数'''（しすう、 {{lang-en-short|''exponent''}}) と呼ぶ<ref>単に「指数」と呼ぶ場合、"exponent" に限らず、（数学に限っても）種々の index を意味する場合も多く、文脈に注意を要する（たとえば[[部分群|部分群の指数]]）。また、（必ずしも冪指数のことでない）"exponent" の訳として冪数が用いられることもある（たとえば[[有限群|有限群の冪数]]）。</ref>。また、必ずしも冪指数とは限らない添字 ''n'' をその基準となる文字 ''x'' の右肩に乗せる[[添字記法]]を指数表記・冪記法などとよぶ場合もある。

厳密には、xのn-乗冪は帰納法を用いて
# ''x''<sup>1</sup> = ''x'',
# ''x''<sup>''n''+1</sup> = ''x''<sup>''n''</sup> × ''x'' &nbsp; (''n'' ≥ 1)

と定義される。

== 指数の拡張と指数法則 ==

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

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

有理数の範囲で[[2の累乗数]]を例に取ると：
*2<sup>4</sup> = [[16]]
*2<sup>3</sup> = [[8]]
*2<sup>2</sup> = [[4]]
*2<sup>1</sup> = [[2]]
*2<sup>0</sup> = [[1]]
*2<sup>&minus;1</sup> = [[1/2]]
*2<sup>&minus;2</sup> = [[1/4]]
*2<sup>&minus;3</sup> = [[1/8]]
*2<sup>&minus;4</sup> = [[1/16]]

ただし、底が0の場合は「0で割れない」などの理由から定義しないのが普通である。
{{Main|0の0乗}}

===累乗根===
自然数 ''m'' に対し、''x'' の ''m'' [[冪根|乗根]]すなわち ''m'' 乗して ''x'' になるような数 ''y'' がただ一つあるならば、その ''y'' を ''x''<sup>1/''m''</sup> とし、自然数または整数 ''n'' に対し
: ''x''<sup>''n''/''m''</sup> = (''x''<sup>1/''m''</sup>)<sup>''n''</sup>
と定めることによって、''x'' を底とする冪乗の指数を[[有理数]]の範囲まで拡張することができる。
このとき、'''指数法則'''と呼ばれる以下の関係式が成り立つ。
* ''x''<sup>''r''+''s''</sup> = ''x''<sup>''r''</sup> × ''x''<sup>''s''</sup> 
* ''x''<sup>''r×s''</sup> = (''x''<sup>''r''</sup>)<sup>''s''</sup> 

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

=== 正の実数の実数べき ===
''x'' が正の実数であれば、上で制限されていた指数への条件は外れる。
なぜなら、正数であれば任意の自然数 ''m'' に対する正の ''m'' 乗根 {{sup|''m''}}√{{overline|''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億までの）自然数や浮動小数点数を扱う場合は下位桁から計算する方式を、前述のような巨大な自然数を扱う場合には上位桁から計算する方式を用いると効率が良い。

=== 下位桁から計算する方式 ===
バイナリ法では、次の性質を利用する。
: (''a''<sup>''x''</sup>)<sup>2</sup> = ''a''<sup>2''x''</sup>
例えば (''a''<sup>8</sup>)<sup>2</sup> = ''a''<sup>16</sup> である。したがって、''a''（すなわち ''a''<sup>1</sup>）から始めて2乗を繰り返すとこうなる。
: ''a''<sup>1</sup> → ''a''<sup>2</sup> → ''a''<sup>4</sup> → ''a''<sup>8</sup> → ''a''<sup>16</sup> → ''a''<sup>32</sup> → …
これらの数のうち、適切なものを選んで掛け合わせれば、任意の累乗を速く（すなわち少ない乗算回数で）計算することができる<ref name="algo">{{cite book | 1=和書 | title=C言語による最新アルゴリズム事典 | publisher=[[技術評論社]] | author=奥村晴彦 | authorlink=奥村晴彦 | year=1991 | page=304 | isbn=4-87408-414-1}}</ref>。例えば ''a''<sup>43</sup> は、上で示した指数法則によって、
: ''a''<sup>43</sup> = ''a''<sup>32+8+2+1</sup> = ''a''<sup>32</sup>×''a''<sup>8</sup>×''a''<sup>2</sup>×''a''<sup>1</sup>
として計算することができる（乗算回数は 8 回で済むので、''a'' を 42 回繰り返し掛け合わせるのに比べて効率がよい）。

<!-- LaTeX の {matrix} を使うことも考えたが、保守性のために表にした -->
{| border="0" cellspacing="0" cellpadding="1"
<!-- |+ バイナリ法による高速な累乗 -->
|-
| align="right" | （十進表記）：
| &nbsp;
| ''a''<sup>1</sup> 
|
| ''a''<sup>2</sup> 
|
| ''a''<sup>4</sup> 
|
| ''a''<sup>8</sup> 
|
| ''a''<sup>16</sup> 
|
| ''a''<sup>32</sup>
|-
| align="right" | 2乗の繰返し（[[二進法|二進表記]]）：
| &nbsp;
| ''a''<sup>1</sup> 
|→
| ''a''<sup>10</sup> 
|→
| ''a''<sup>100</sup> 
|→
| ''a''<sup>1000</sup> 
|→
| ''a''<sup>10000</sup> 
|→
| ''a''<sup>100000</sup>
|-
| &nbsp;
| &nbsp;
| ↓ 
|
| ↓ 
|
| &nbsp; 
|
| ↓ 
|
| &nbsp; 
|
| ↓
|-
| align="right" | 累乗の計算（二進表記）：
| &nbsp;
| ''a''<sup>1</sup> 
|→
| ''a''<sup>11</sup> 
|→
| →→
|→
| ''a''<sup>1011</sup> 
|→
| →→→
|→
| ''a''<sup>101011</sup>
|-
| &nbsp; <!-- align="right"（十進数表記）： -->
| &nbsp;
|
|
|
|
|
|
|
|
|
| align="right" | ＝
| ''a''<sup>43</sup>
|}

[[コンピュータ]]の[[アルゴリズム]]として書くとこうなる。下位桁から順に扱うことから、順に2で割ると同時にその余りを求め（実際にはシフト演算を用い）ながら演算を行うことで二進表記を省略し、効率を高める。
# 指数を <math>n</math> とし、2乗していく値 p := a 、結果値 v := 1 とする。 
# n が 0 なら、v を出力して終了する。 
# n の最下位桁が 1 なら、v := v * p とする。 
# 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であるか否かと一致する。

コンピュータのアルゴリズムとして書くとこうなる。
# 指数 <math>n</math> を二進表記したものを n とし、n の最下位桁を n[0]、最上位桁を n[m]、最下位から数えて k 桁目を n[k] と表記する。
# 結果値 v := 1 とし、
# k := m とする（最上位）。
# v := v * v
# n[k] が 1 ならば v := v * ''a'' とする。
# k := k - 1
# k ≧ 0 なら 4. に戻る。

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

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

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

== 脚注 ==
{{reflist}}

== 関連項目 ==
*[[指数関数]] - 冪指数を[[実数]]へ拡張し、連続関数としたもの
*[[冪根]]（累乗根）
*[[順序数#冪|順序数]]
*[[平方数]]
*[[立方数]]
*[[冪級数]]
*[[冪集合]]
*[[冪零行列]]
*[[2の冪]]
*[[冪剰余]]
*[[ゼロ除算]]
*[[0の0乗]]
*[[冪乗則]]
*[[テトレーション]]

{{二項演算}}

{{DEFAULTSORT:へきしよう}}
[[Category:算術]]
[[Category:数学に関する記事]]
{{Link GA|en}}
{{Link FA|he}}