冪乗

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動先: 案内検索
演算の結果
加法 (+)
加法因子 + 加法因子 =
被加数 + 加数 = 和
減法 (−)
被減数 − 減数 =
乗法 (×)
因数 × 因数 =
被乗数 × 乗数 = 積
倍率 × 被乗数 = 積
除法 (÷)
被除数 ÷ 除数 =
被約数 ÷ 約数 = 商
実 ÷ 法 = 商
分子/分母 = 商
剰余算 (mod)
被除数 mod 除数 = 剰余
被除数 mod 法 = 剰余
冪指数 = 冪
冪根 (√)
次数被開方数 = 冪根
対数 (log)
log(真数) = 対数

冪演算(べきえんざん、: : : Exponentiation)は、 (base) および冪指数 (exponent) と呼ばれる二つのに対して定まる数学算法である。通常は、冪指数を底の右肩につく上付き文字によって示す。自然数 n を冪指数とする冪演算は(るいじょう、: repeated multiplication) に一致する。

具体的に、英語版 b および冪指数 n を持つ冪 (power) bn は、n が自然数(正整数)のとき、底の累乗

b^n = \underbrace{b \times \cdots \times b}_{n\text{ factors}}

で与えられる。このとき bnbn-乗とか、n-次の b-冪などと呼ばれる。

よく用いられる冪指数に対しては、固有の名前が与えられているものがある。例えば冪指数 2 に対して二次の冪(二乗) b2b平方 (square of b) あるいは b-自乗 (b-squared) と呼ばれ、冪指数 3 に対する三次の冪 b3b立方 (cube of b, b-cubed) と呼ばれる。また冪指数 −1 に対して冪 b−11/b であり b逆数(あるいは乗法逆元)と呼ばれる。一般に負の整数 n に対して底 b が零でないとき、冪 bn はふつう bn × bm = bn + m なる性質を保つように bn := 1/bn と定義される。

冪演算は任意の実数あるいは複素数を冪指数とするように定義を拡張することができる。整数冪に限れば、行列などを含めた非常に多種多様な代数的構造に対しても冪を定義することができる。

冪乗を長さや面積でイメージするヒント

記法の歴史[編集]

用語「冪」(power) はギリシアの数学者エウクレイデスが直線の平方を表すのに用いた語に起源がある[1]アルキメデス10 の冪を扱うために必要となる指数法則 10a • 10b = 10a+b を発見し証明した[2]。9世紀、ペルシアの数学者アル゠フワーリズミは平方を mal, 立方を kab で表した。これを後に中世イスラムの数学者がそれぞれ m, k で表す記法として用いていることが、15世紀ごろのアル゠カラサディ英語版の仕事に見ることができる[3]

16世紀後半、ヨスト・ビュルギは冪指数をローマ数字を用いて表した[4]

17世紀初頭、今日用いられる現代的な冪記法の最初の形はルネ・デカルトが著書 La Géométrie の一巻において導入した[5]

15世紀にニコラ・ショケ英語版は冪記法の一種を用い、それは後の16世紀にハインリヒ・シュライベル英語版およびミハエル・スティーフェル英語版が用いている。語 "exponent"(冪数)は1544年にミハエル・スティーフェルが造語したもので[6]サミュエル・ジーク英語版は1696年に語 indices(指数)を導入している[1]。16世紀にロバート・レコード英語版は square(二次), cube(三次), zenzizenzic(四次英語版), sursolid(五次), zenzicube(六次), second sursolid(七次), zenzizenzizenzic(八次英語版)の語を用いた[7]。四乗については Biquadrate(複二次)の語も用いられた。

アイザック・ニュートンなど一部の数学者は冪指数は二乗よりも大きな冪に対してのみ用い、平方は反復積として書き表した。これは例えば ax + bxx + cx3 + d のように多項式を書くということである。

歴史的にはもう一つ involution が同義語として用いられていた[8]が現在では稀であり、現在別の意味で用いられているので混同すべきではない。

誤用としての「べき乗」と語の歴史[編集]

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

この際、n 乗を取る操作の伝統的名称である「n 乗冪」[10] と「累乗」が混同され、「冪乗(べきじょう)」という語を生じた。一方で、「冪剰余」「冪集合」などの高等学校以下で扱われない概念に対しては、「冪」の部分が「べき乗」に置き換えられることはなく、例えば「べき乗集合」などといった表現は生じていない。

定義[編集]

自然数冪[編集]

実数(など積 \times の定義された)において、元 x 、および、自然数 n に対して xn

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

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

また、これら操作を「xn 乗 (etc.) を取る」などと称し、特に n を固定して x を入力とする関数と見るときは、冪関数という。 x の 2乗、3乗は特に、それぞれ x の平方 (へいほう、 : square)、立方 (りっぽう、 : cube) と呼ばれ、2乗を特に自乗という場合もある。

xn において、x(てい、: base基数)と呼び、n冪数冪指数または単に指数(しすう、 : exponent) と呼ぶ[11]。また、必ずしも冪指数とは限らない添字 n をその基準となる文字 x の右肩に乗せる添字記法を指数表記・冪記法などとよぶ場合もある。

厳密には、xn-乗冪は

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

によって再帰的に定義される。

負の整数冪[編集]

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

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

ただし、底が0の場合は「0で割れない」などの理由から定義しないか、あるいは 00 については 1 と定義するのが一般的である。

有理数冪[編集]

自然数 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 を分母とする有理数である。

実数冪[編集]

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

x^{n/m} = \bigl(\!\sqrt[m]{x}\,\bigr)^n = \sqrt[m]{x^n}

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

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

複素数冪[編集]

複素数 z に対し、

e^z:=\sum_{n=0}^\infty \frac{z^n}{n!}

と定める。この級数は任意の複素数 z に対して収束する。z = x + iyx, y は実数)と表すと、

e^{x+iy}=e^x(\cos y+i\sin y)

が成り立つ。

さらに、この関数の「逆関数」を log と書けば、一般の複素数 w ≠ 0 に対し

w^z:=e^{z\log w}

と定義される。これは log が多価関数であるため一般には値が 1 つには定まらない。ただし、w = e の場合には、上に冪級数で定義した方の意味で用いるのが普通である。

性質[編集]

  • 冪演算は可換でない(たとえば 23 = 8 ≠ 9 = 32)。また結合的でない(たとえば (31)3 = 27 ≠ 3 = 3(13))。
  • 括弧を用いずに abc と書いたときには、これはふつう a(bc) を意味する。すなわち冪演算は右結合的である(演算子の優先順位も参照)。

指数法則[編集]

以下の一覧表において多重定義の虞を除くため、底は非零実数であるような冪のみを考える。ただし、正の冪のみを考えるならば、底が 0 でも各法則は成り立つ。また以下の一覧において、有理数について分母が奇数あるいは偶数であるというときは、常にその有理数の既約分数表示における分母のことを言っているものとする。

指数法則
規則 条件
a^0 = 1 a ≠ 0 は任意
 a^{-r} = \frac{1}{a^r}
  • a > 0 ならば r は任意の実数
  • a < 0 ならば r は分母が奇数の任意の有理数
a^{\frac{m}{n}} = \sqrt[n]{a^m}=(\sqrt [n] a)^m
  • a > 0 ならば n は任意の自然数で m は任意の整数
  • a < 0 ならば n は任意の奇数で m は任意の整数
a^{r+s} = a^r\cdot a^s
  • a > 0 ならば r, s は任意の実数
  • a < 0 ならば r, s は分母が奇数の任意の有理数
a^{r-s}=\frac{a^r}{a^s}
  • a > 0 ならば r, s は任意の実数
  • a < 0 ならば r, s は分母が奇数の任意の有理数
(a\cdot b)^r = a^r\cdot b^r
  • a  • b ≠ 0 ならば r は任意の自然数、あるいは任意の整数
  • a > 0, b > 0 ならば r は任意の実数
  • a, b の少なくとも一方が負ならば r は分母が奇数の任意の有理数
\left(\frac{a}{b}\right)^r = \frac{a^r}{b^r}
  • 整数 r に対して、[r ≥ 0 かつ b ≠ 0] または [r ≤ 0 かつ a ≠ 0] のとき
  • a > 0, b > 0 ならば r は任意の実数
  • a, b の少なくとも一方が負ならば r は分母が奇数の任意の有理数
(a^r)^s = a^{r\cdot s}
  • a ≠ 0 ならば r, s は任意の整数
  • a > 0 ならば r, s は任意の実数
  • a < 0 ならば r, s は分母が奇数の任意の有理数
(a^r)^s =- a^{r\cdot s} a < 0 かつ有理数 r, s に対して、r および r  • s は分母が奇数、かつ r  • s の分子が奇数のとき
(ar)s = ±ar • s に関して
  • 冪指数 r, s の少なくとも一方が無理数であるとき、あるいはこれらの双方が有理数だが r または r  • s の少なくとも一方の分母が偶数となるときには、a < 0 に対する (ar)s または ar • s は定義されない。それ以外のとき、この両者は定義されて符号の違いを除いて一致する。特に両者は a > 0 ならば任意の実数 r, s に対して一致し、また a ≠ 0 ならば任意の整数 r, s に対して一致する。
  • a < 0 かつ r, s が整数でない有理数であるときには可能性は二通り考えられ、どちらになるかは r の分子と s の分母の素因数分解が関係する。式 (ar)s = ±ar • s の右辺の符号は何れが正しいのかを知るには a = −1 のときを見れば十分である(与えられた r, s に対して a = −1 のとき正しくなる方の符号をとれば、任意の a < 0 についても成り立つ)。
  • a < 0 に対して (ar)s = −ar • s が適用されるならば、a ≠ 0 に対して (ar)s = |a|r • s が成り立つ(冪指数が正ならば a = 0 のときも成り立つ)。

例えば、((−1)2)12 = 1 および (−1)2 • 12 = −1 であるから、a < 0 に対して a2 = (a2)12 = −a2 • 12 = −a, したがって任意の実数 a に対して a2 = |a| が成り立つ。

一般化[編集]

モノイドにおける冪[編集]

冪演算は任意の半群において定義できる[12]モノイドは単位元を持つ半群、すなわち適当な集合 X を台として合成あるいは乗法と呼ばれる二項演算が定義される代数系であって、その乗法が結合法則を満足し、かつ乗法単位元 1 を持つものを言う。モノイドにおける自然数冪は

  • x^0=1\quad (\forall x\in X),
  • x^{n+1}=x^nx\quad (x\in X,\,n\in \mathbb{Z}_{\ge 0})

として帰納的に定義することができる。特に先の式(零乗すること)は「単位元を持つ」ことによって初めて意味を成す規約であることに注意すべきである(空積も参照のこと)。

モノイドの例には(の乗法モノイド)のような数学的に重要な多くの構造が含まれ、またより特定の例として行列環の場合について後述する。

行列および線型作用素の冪[編集]

正方行列 A に対して A 自身の n 個のを行列の冪と呼ぶ。また A0 は単位行列に等しいものと定義され[13]、さらに A が可逆ならば An := (A−1)n と定義する。

行列の冪は離散力学系英語版の文脈でしばしば現れる。そこでは行列 A は適当な系の状態ベクトル x を次の状態 Ax へ遷移させることを表す[14]。これは例えばマルコフ連鎖の標準的な解釈である。これにより、A2x は二段階後の系の状態であり、以下同様に Anxn 段階後の系の状態と理解される。つまり行列の冪 An は現在と n 段階後の状態の間の遷移行列であって、行列の冪を計算することはこの力学系の発展を解くことに等しい。便宜上、多くの場合において行列の冪は固有値と固有ベクトルを用いて計算することができる。

行列を離れてより一般の線型作用素にも冪演算は定められる。例えば微分積分学における微分演算 d/dx は函数 f に作用して別の函数 df/dx = f' を与える線型作用素であり、この作用素の n-乗は n-階微分

\left(\frac{d}{dx}\right)^nf(x) = \frac{d^n}{dx^n}f(x) = f^{(n)}(x)

である。これは線型作用素の離散的な冪の例であるが、作用素の連続的な冪が定義できたほうがよい場面が多く存在する。C0-半群の数学的理論はこのような事情を出発点としている[15]。離散冪指数に対する行列の冪の計算が離散力学系を解くことであったのと同様に、連続冪指数に対する作用素の冪の計算は連続力学系を解くことに等しい。そういった例として熱方程式シュレーディンガー方程式波動方程式あるいはもっとほかの時間発展を含む偏微分方程式を挙げることができる。このような冪演算の特別の場合として、微分演算の非整数乗は分数階微分と呼ばれ、分数階積分英語版とともに、分数階微分積分学の基本演算の一つとなっている。

有限体における冪[編集]

は、四則演算が矛盾なく定義されそれらの馴染み深い性質が満足されるような代数的構造である。例えば実数全体は体を成す。複素数の全体、有理数の全体などもそうである。これら馴染み深い例が全て無限集合であるのと異なり、有限個の元しか持たない体も存在する。そのもっとも簡単な例が二元体 F2 = {0,1} で、加法は 0 + 1 = 1 + 0 = 1, 0 + 0 = 1 + 1 = 0 および乗法は 0  • 0 = 1  • 0 = 0  • 1 = 0, 1  • 1 = 1 で与えられる。

有限体における冪演算は公開鍵暗号に応用を持つ。例えばディフィー・ヘルマン鍵交換は、有限体における冪は計算量的にコストが掛からないのに対し、冪の逆である離散対数は計算量的にコストが掛かるという事実を用いている。

任意の有限体 F は、素数 p がただ一つ存在して、任意の xF に対して px = 0 が成り立つ(xp 個加えれば零になる)という性質を持つ。例えば二元体 F2 では p = 2 である。この素数 p はその体の標数と呼ばれる。F を標数 p の体として F の各元を p-乗する写像 f(x) = xp を考える。これは Fフロベニュース自己準同型と呼ばれる。新入生の夢英語版(幼稚な二項定理)とも呼ばれる等式 (x + y)p = xp + yp がこの体においては成り立つため、フロベニュース自己準同型が実際に体の自己準同型を与えるものであることが確認できる。フロベニュース自己準同型は F の素体上のガロワ群の生成元であるため数論において重要である。

抽象代数学における冪[編集]

冪指数が整数であるような冪演算は抽象代数学における極めて一般の構造に対して定義することができる。

集合 X は乗法的に書かれた冪結合的英語版二項演算を持つもの:

(x^i x^j) x^k = x^i (x^j x^k) \quad (\forall x\in X)

とするとき、任意の xX と任意の自然数 n に対して冪 xn は、xn 個のコピーの積を表すものとして

\begin{align}
  x^1 &= x \\
  x^n &= x^{n-1}x \quad(n > 1)
\end{align}

のように帰納的に定義される。これは以下のような性質

\begin{align}
 x^{m+n} &= x^m x^n \\
 (x^m)^n &= x^{mn}
\end{align}

を満足する。さらに、考えている演算が両側単位元 1 を持つ:

\exists! 1 \text{ s.t. } x1 = 1x = x \quad (\forall x\in X)

ならば x0 は任意の x に対して 1 に等しいものと定義する。[要出典]

さらにまた演算が両側逆元を持ち、なおかつ結合的

\begin{align}
 x x^{-1} &= x^{-1} x = 1,\\
  (x y) z &= x (y z)
\end{align}

ならばマグマ Xを成す。このとき x の逆元を x−1 と書けば、冪演算に関する通常の規則

\begin{align}
  x^{-n} &= \left(x^{-1}\right)^n \\
 x^{m-n} &= x^m x^{-n}
\end{align}

はすべて満足される。また(例えばアーベル群のように)乗法演算が可換ならば

(xy)^n = x^n y^n

も満足される。(アーベル群が通常そうであるように)二項演算を加法的に書くならば、「冪演算は累乗(反復乗法)である」という主張は「乗法は累加(反復加法)である」という主張に引き写され、各指数法則は対応する乗法法則に引き写される。

一つの集合上に複数の冪結合的に項演算が定義されるときには、各演算に関して反復による冪演算を考えることができるから、どれに関する冪かを明示するために上付き添字に反復したい演算を表す記号を併置する方法がよく用いられる。つまり演算 および # が定義されるとき、xn と書けば x ∗ … ∗ x を意味し、x#n と書けば x # … # x を意味するという具合である。

上付き添字記法は、特に群論において、共軛変換を表すのにも用いられる(即ち、g, h を適当な群の元として gh = h−1gh)。この共軛変換は指数法則と同様の性質を一部満足するけれども、これはいかなる意味においても反復乗法としての冪演算の例ではない。カンドルはこれら共軛変換の性質が中心的な役割を果たす代数的構造である。

集合の冪[編集]

デカルト冪[編集]

自然数 n と任意の集合 A に対して、式 An はしばしば A の元からなる順序 n-全体の成す集合を表すのに用いられる。これは An は集合 {0, 1, 2, …, n−1} から集合 A への写像全体の成す集合であると言っても同じことである(n-組 (a0, a1, a2, …, an−1)iai へ送る写像を表す)。

無限基数 κ と集合 A に対しても、記号 Aκ は濃度 κ の集合から A への写像全体の成す集合を表すのに用いられる。基数の冪との区別のために κA と書くこともある。

反復直和[編集]

一般化された冪は、複数の集合上で定義される演算や追加の構造を持つ集合に対しても定義することができる。例えば、線型代数学において勝手な添字集合上でのベクトル空間直和を考えることができる。つまり Vi をベクトル空間として

\bigoplus_{i \in \mathbb{N}} V_{i}

を考えるとき、任意の i について Vi = V とすれば得られる直和を冪記法を用いて VN あるいは直和の意味であることが明らかならば単に VN のように書くことができる。ここで再び集合 N を基数 n で取り替えれば Vn を得る(濃度 n を持つ特定の標準的な集合を選ぶことなしに、これは同型を除いてのみ定義される)。V として実数体 R を(それ自身の上のベクトル空間と見て)とれば、n を適当な自然数として線型代数学でもっともよく調べられる実ベクトル空間 Rn を得る。

配置集合[編集]

冪演算の底を集合とするとき、何も断りがなければ冪演算はデカルト積である。複数の集合のデカルト積は n-組を与え、n-組は適当な濃度を持つ集合上で定義された写像として表すことができるのだから、この場合冪 SN は単に N から S への写像全体の成す集合

S^N \equiv \{ f\colon N \to S \}

である。この定義は |SN| = |S||N| が満たされるという意味で基数の冪と整合する。ただし |X|X の濃度を表す。"2" を集合 {0, 1} として定義すれば |2X| = 2|X| が得られる。ここに 2XX冪集合であり、普通は 𝒫(X) などで表される。

圏論における冪対象[編集]

デカルト閉圏において、任意の対象に対して別の任意の対象を冪指数とする冪演算を冪対象によって与えることができる。集合の圏英語版における冪対象は配置集合であるから、これはその一般化になっている。考えている圏に始対象 0 が存在するならば、冪対象 00 は任意の終対象 1 に同型である。

順序数・基数の冪[編集]

集合論では基数順序数の冪演算も定義される。

基数 κ, λ に対して冪 κλ は基数 λ の任意の集合から基数 κ の任意の集合への写像全体の成す集合の基数を表す[16]κ, λ がともに有限ならばこれは通常の算術的な(つまり自然数の)冪演算と一致する(たとえば、二元集合から元を取って得られる三つ組全体の成す集合の基数は 8 = 23 で与えられる)。基数の算術において κ0 は常に(特に κ が無限基数や 0 であるときでさえ)1 である。

基数の冪は順序数の冪とは異なる。後者は超限帰納法を含む過程の極限として定義される。

反復冪[編集]

自然数冪が乗法の反復として考えられたことと同様に、冪演算を繰り返す演算というものを定義することもできる。それをまた反復すれば別の演算が定義され、同様に繰り返してハイパー演算の概念を得る。このようにして得られるハイパー演算の列において、次の演算は前の演算に対して急速に増大する。

写像の冪の記法に関する注意[編集]

合成冪[編集]

写像の冪乗となるべきものとして、写像を表す符牒の直後に整数の上付き添字を添えたとき、それは(反復乗法ではなくて)反復合成冪の意味で用いることがよく行われる。つまり例えば f3(x)f(f(f(x))) の意味であり、また特に f−1(x)f逆写像を意味するのが普通である。反復合成写像はフラクタル力学系の研究において興味を持たれる。チャールズ・バベッジ写像の平方根 f 1/2(x) を求める問題を研究した最初の人であった。

値ごとの冪[編集]

しかし歴史的経緯により、三角函数の場合には、函数の略号に正の冪指数を添えたときは函数の値に対して冪を取ることを意味する一方で、−1 を冪指数としたときは逆函数を意味するという特別な文法が適用される。つまり、 sin2x(sin x)2 を括弧を用いずに略記する方法に過ぎない一方、sin−1x逆正弦函数 arcsin x を意味するのである。三角函数の逆数函数は(例えば 1/(sin x) = (sin x)−1 = csc x のように)それぞれ固有の名前と略号が与えられているから、三角函数の逆数の略記法は無用である。同様の規約は対数函数にも適用され、log2x はふつう (log x)2 の意味であって log log x の意味でない。

上付き添字[編集]

添字付けられた変数を考えるとき、その変数の添字を上付きにする場合があり、それはあたかも冪であるかのような印象を受けるかもしれないが混同するべきではない。これは特にテンソル解析においてベクトル場の座標表示などで現れる。あるいはまた数列のような、既にそれ自身添字付けられているような量に対してさらに添字付けを行う場合にもしばしば用いられる。

高階導函数[編集]

函数 fn-階導函数はふつう f(n) と書かれるように、冪記法は冪指数を括弧で囲んで書くこともある。

効率的な演算法[編集]

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

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

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

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

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

(a^x)^2 = a^{2x}

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

a^1 \to a^2 \to a^4 \to a^8 \to a^{16} \to a^{32} \to \cdots

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

a^{43} = a^{32+8+2+1} = a^{32} \times a^8 \times a^2 \times a^1

として計算することができる(乗算回数は 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} = (a^x)^2

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

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

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

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

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

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

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

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

以下同様に、

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

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

a^{43} = ( ( ( ( ( a )^2 )^2 \cdot a )^2 )^2 \cdot a )^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. ^ a b O'Connor, John J.; Robertson, Edmund F., “Etymology of some common mathematical terms”, MacTutor History of Mathematics archive, University of St Andrews, http://www-history.mcs.st-andrews.ac.uk/Miscellaneous/Mathematical_notation.html .
  2. ^ For further analysis see The Sand Reckoner.
  3. ^ O'Connor, John J.; Robertson, Edmund F., “Abu'l Hasan ibn Ali al Qalasadi”, MacTutor History of Mathematics archive, University of St Andrews, http://www-history.mcs.st-andrews.ac.uk/Biographies/Al-Qalasadi.html .
  4. ^ Cajori, Florian (2007). A History of Mathematical Notations; Vol I. Cosimo Classics. Pg 344 ISBN 1602066841
  5. ^ René Descartes, Discourse de la Méthode ... (Leiden, (Netherlands): Jan Maire, 1637), appended book: La Géométrie, book one, page 299. From page 299: " ... Et aa, ou a2, pour multiplier a par soy mesme; Et a3, pour le multiplier encore une fois par a, & ainsi a l'infini ; ... " ( ... and aa, or a2, in order to multiply a by itself; and a3, in order to multiply it once more by a, and thus to infinity ; ... )
  6. ^ See:
    • Earliest Known Uses of Some of the Words of Mathematics
    • Michael Stifel, Arithmetica integra (Nuremberg ("Norimberga"), (Germany): Johannes Petreius, 1544), Liber III (Book 3), Caput III (Chapter 3): De Algorithmo numerorum Cossicorum. (On algorithms of algebra.), page 236. Stifel was trying to conveniently represent the terms of geometric progressions. He devised a cumbersome notation for doing that. On page 236, he presented the notation for the first eight terms of a geometric progression (using 1 as a base) and then he wrote: "Quemadmodum autem hic vides, quemlibet terminum progressionis cossicæ, suum habere exponentem in suo ordine (ut 1ze habet 1. 1ʓ habet 2 &c.) sic quilibet numerus cossicus, servat exponentem suæ denominationis implicite, qui ei serviat & utilis sit, potissimus in multiplicatione & divisione, ut paulo inferius dicam." (However, you see how each term of the progression has its exponent in its order (as 1ze has a 1, 1ʓ has a 2, etc.), so each number is implicitly subject to the exponent of its denomination, which [in turn] is subject to it and is useful mainly in multiplication and division, as I will mention just below.) [Note: Most of Stifel's cumbersome symbols were taken from Christoff Rudolff, who in turn took them from Leonardo Fibonacci's Liber Abaci (1202), where they served as shorthand symbols for the Latin words res/radix (x), census/zensus (x2), and cubus (x3).]
  7. ^ Quinion, Michael. “Zenzizenzizenzic - the eighth power of a number”. World Wide Words. 2010年3月19日閲覧。
  8. ^ This definition of "involution" appears in the OED second edition, 1989, and Merriam-Webster online dictionary [1]. The most recent usage in this sense cited by the OED is from 1806.
  9. ^ 王青翔 (1999), 「算木」を超えた男, 東京: 東洋書店, ISBN 4-88595-226-3 
  10. ^ {関孝和}
  11. ^ 単に「指数」と呼ぶ場合、"exponent" に限らず、(数学に限っても)種々の index を意味する場合も多く、文脈に注意を要する(たとえば部分群の指数)。また、(必ずしも冪指数のことでない)"exponent" の訳として冪数が用いられることもある(たとえば群の冪数英語版)。
  12. ^ Nicolas Bourbaki (1970). Algèbre. Springer. , I.2
  13. ^ Chapter 1, Elementary Linear Algebra, 8E, Howard Anton
  14. ^ Strang, Gilbert (1988), Linear algebra and its applications (3rd ed.), Brooks-Cole , Chapter 5.
  15. ^ E Hille, R S Phillips: Functional Analysis and Semi-Groups. American Mathematical Society, 1975.
  16. ^ N. Bourbaki, Elements of Mathematics, Theory of Sets, Springer-Verlag, 2004, III.§3.5.
  17. ^ 奥村晴彦 『C言語による最新アルゴリズム事典』 技術評論社1991年、304頁。ISBN 4-87408-414-1

関連項目[編集]