数学における冪乗(べきじょう、べき乗、英: 仏: 独: exponentiation)または冪演算(べきえんざん)は、底 (てい、英: base) および冪指数 (べきしすう、英: exponent) と呼ばれる二つの数に対して定まる数学的算法である。その結果は冪 (べき、英: power) と呼ばれる。表現の揺れにより同じ概念は日本語で「累乗」とも表現されており、初等教育ではこちらの表現のほうが多くなっている(本文参照)。
概要
底 b および冪指数 e をもつ冪は、底の右肩に冪指数を乗せて be のように書かれる。
であり、bn は b の n-乗や、n-次の b-冪などと呼ばれる。
特定の冪指数に対して、固有の名前が付けられている。例えば、冪指数が 2 である冪(2 乗) b2 は「b の平方 (square of b)」または「b-自乗 (b-squared)」と呼ばれ、冪指数が 3 である冪(3 乗) b3 は「b の立方 (cube of b, b-cubed)」と呼ばれる。それ以降は 4 乗、5 乗、… というように「n 乗」という言い方が一般的である。
冪指数が −1 である冪 b−1 は 1/b であり、「b の逆数」(または乗法逆元)と呼ばれる。一般に冪指数が負の整数 n である冪 bn は、bn × bm = bn + m という性質を保つように、底 b が 0 でないとき bn := 1/b−n と定義される。
冪乗は、任意の実数または複素数を冪指数とするように定義を拡張することができる。底および冪指数が実数である冪において、底を固定して冪指数を変数と見なせば指数函数であり、冪指数を固定して底を変数と見なせば冪函数である。整数乗の冪に限れば、行列などを含めた多種多様な代数的対象に対してもそれを底とする冪を定義することができる。冪指数まで同種の対象に拡張すると、その上で定義された自然指数函数と自然対数函数をもつ完備ノルム環(例えば実数全体 R や複素数全体 C など)を想定するのが自然である。
歴史
歴史上に冪が現れたのは非常に古く、B.C.16世紀ごろに作成された粘土板には平方数表、平方根表、立方根表や三平方の定理について書かれており[1]、エジプト、インド、ギリシアなどでも冪の概念は明示されている。一方で、指数法則に言明する文献は見当たらず「指数概念」には未だ到達していないと考えるべきであるが、冪を意味する英単語 "power" はギリシアの数学者エウクレイデス(ユークリッド)が直線の平方を表すのに用いた語に起源がある[2]。また、「原論」において指数法則 am × an = am+n に相当する命題に言及している[1]が、この時代には算式は発明されておらず、すべて言葉で表現していた[1]。
記法
アルキメデスは 10 の冪を扱うために必要となる指数法則 10a • 10b = 10a + b を発見し、証明した(『砂粒を数えるもの』を参照)。9世紀に、ペルシアの数学者アル゠フワーリズミは平方を mal, 立方を kab で表した。これを後に中世イスラムの数学者がそれぞれ m, k で表す記法として用いていることが、15世紀ごろのアル゠カラサディの仕事に見ることができる[3]。
16世紀後半、ヨスト・ビュルギは冪指数をローマ数字を用いて表した[4]。
17世紀初頭、今日用いられる現代的な冪記法の最初の形は、ルネ・デカルトが著書 La Géométrie の一巻において導入した[5]。
アイザック・ニュートンなど一部の数学者は冪指数は 2 乗よりも大きな冪に対してだけ用い、平方は反復積として書き表した。例えば、多項式を ax + bxx + cx3 + d のように書いた。
用語
15世紀にニコラ・ショケは冪記法の一種を用い、それは後の16世紀にハインリヒ・シュライベルおよびミハエル・スティーフェルが用いている。
16世紀にロバート・レコードは、square(二次), cube(三次), zenzizenzic(四次), sursolid(五次), zenzicube(六次), second sursolid(七次), zenzizenzizenzic(八次)の語を用いた[6]。4 乗については biquadrate(複二次)の語も用いられた。
歴史的には "involution" が冪の同義語として用いられていた[7]が現在では稀であり、別の意味(対合)で用いられているので混同すべきではない。
冪指数
冪の肩に書かれる数のことを冪指数と呼ぶ[8]が、冪指数を意味する用語として、英語ではしばしば exponent と index が同義語として用いられる。この用語選定は18世紀、19世紀を通じて極めて曖昧で個人の嗜好に委ねられていた[9]。しかし、ガウスは、その著書 Disquisitiones Arithmeticae において通常の冪指数と数論的な指数を峻別する必要性から exponens は通常の冪指数、index は数論的な指数を表すものとして明確に区別し使い分けて解説に使用しており、この使い分けはディリクレ、デデキント、ヒルベルトを通じて数論の世界での標準となった[9]。
もとをたどれば、1544年にミハエル・スティーフェルがラテン語: "exponens" を造語し[10][11]、対して1586年にラザルス・シェーナーが数学者ペトルス・ラムスの書籍への補注としてラテン語: "index" を(スティーフェルが exponens と呼んだものと同じものを指す意味で)用いた[12]のがそれぞれの語源と考えられる。exponent と index はこれらの英語翻訳であり、例えば index はサミュエル・ジークが1696年に導入した[2]。
exponent と index の微妙な使い分けと併用の時代はここから始まり、その併用のされ方は国と時代だけでなく個人によっても異なった。イギリスは当初 index が優勢であり、これは聖バーソロミューの大虐殺で殉死したラムスの著作がプロテスタント諸国で非常に人気を集めたからだとの指摘がある[13]。
日本語「冪」
『冪』の字義は「覆う、覆うもの」であって、『冖』と同音同義である。江戸時代の和算家は「冪」の略字として「巾」を用いていた[14]。
第二次世界大戦後の漢字制限政策のもと、これらの字は常用漢字・当用漢字に含まれず、1950年代以降の学習参考書などの出版物では仮名書きで「べき乗」または「累乗」への書き換えが進められ、結果として初等数学の教科書ではもっぱら「累乗」が用いられた。
「冪集合」、「冪級数」などの高等学校以下で扱われない多くの概念に対しては、「冪」の部分が置き換えられることはなく、例えば「べき乗集合」や「累乗集合」などといった表現はあまり生じていない。
定義
自然数乗冪
実数(または積 の定義された群、より一般には半群)において、元 x と自然数 n に対して xn を
で定義する(厳密には再帰的に定義する)。 上付きの n が書けない場合には、 x^n という表記を用いることが多い。
この操作を「x の n 乗を取る」などといい、特に n を固定して x を入力とする関数(特に実数 x の函数)と見るときは、冪関数という。 x の 2乗、3乗は特に、それぞれ x の平方 (へいほう、 英: square)、立方 (りっぽう、 英: cube) と呼ばれ、2乗を特に自乗という場合もある。
冪 xn において、x を底(てい、英: base、 基数)と呼び、n を冪数、冪指数または単に指数(しすう、 英: exponent) と呼ぶ[注釈 1]。必ずしも冪指数とは限らない添字 n をその基準となる文字 x の右肩に乗せる添字記法を指数表記・冪記法などとよぶ場合もある。
厳密には、x の n 乗冪は
- x1 = x,
- xn+1 = xn × x (n ≥ 1)
によって再帰的に定義される。
負の整数乗冪
帰納的定義を見れば下のように拡張するのが自然である。
有理数の範囲で2の冪を例に取ると:
ただし、底が 0 の場合は「0 で割れない」などの理由から定義しないか、または 00 については 1 と定義するのが一般的である。
有理数乗冪
自然数 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 乗根 がただ一つ存在するので、正の有理数 に対し
と定めることができる。さらに、x が 0 でなければ逆元が存在するので、指数は有理数全体まで拡張される。
x (>0) の冪は、その指数に関して極限を取ることによって実数上の関数に拡張され、連続関数になる。連続な拡張は一意であり、これを x を底とする指数関数と呼ぶ。
複素数乗冪
複素数 z に対して、函数 exp を級数
で定義する。この級数は任意の複素数 z に対して収束する。特に exp(1) ≕ e は自然対数の底に等しく、任意の実数 x に対して exp(x) = ex(右辺は実数 e の実数 x 乗の意)である(したがって任意の複素数に対して ez ≔ exp(z) とも書かれる[注釈 2])。z ≔ x + iy (x, y は実数)と表すと、
が成り立つ(cis は純虚指数函数)。特に eiy = cos(y) + i⋅sin(y) はオイラーの公式と呼ばれる関係式である。
さらに、この関数の「逆関数」を log と書けば、一般の複素数 w ≠ 0 に対して
と定義される。log が多価関数なので、一般には値が 1 つには定まらない。ただし、w = e の場合には、上の冪級数で定義したほうの意味で用いるのが普通である。
性質
- 冪演算は可換でない(たとえば 23 = 8 , 32 = 9 , 8≠9.)。また結合的でない(たとえば (23)2 = 64 , 512 = 2(32) , 64≠512.)。
- 括弧を用いずに abc と書いたときには、これはふつう a(bc) を意味する。すなわち冪演算は右結合的である(これは優先順位(precedence, 演算子の優先順位)ではなく、演算子の結合性(associativity, en:Operator associativity)のことである)。
指数法則
以下の一覧表において多重定義の虞を除くため、底は非零実数であるような冪のみを考える。ただし、正の冪のみを考えるならば、底が 0 でも各法則は成り立つ。また以下の一覧において、有理数について分母が奇数あるいは偶数であるというときは、常にその有理数の既約分数表示における分母のことを言っているものとする。
規則 | 条件 |
---|---|
a ≠ 0 は任意 | |
| |
| |
| |
| |
| |
| |
| |
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)1⁄2 = 1 および (−1)2 • 1⁄2 = −1 であるから、a < 0 に対して √a2 = (a2)1⁄2 = −a2 • 1⁄2 = −a, したがって任意の実数 a に対して √a2 = |a| が成り立つ。
指数・対数法則の不成立
正の実数に対する冪および対数に関する等式のいくつかは、複素数冪や複素対数がどのように一価函数として定義されようとも、複素数に対しては成り立たないことが起こる。
- 等式 log(bx) = x⋅log(b) は b が正の実数で x が実数のときにはいつでも成り立つ。しかし、複素対数の主枝に対して
は反例になる。複素対数のどの枝を用いたかに関わらず、この等式には同様の反例が存在する。(この結果のみを使うものとすれば)
であるとまでしか言えない。
この等式は log を多価函数と考えるときでさえ成り立たない。log(wz) の取り得る値は z⋅log(w) の取り得る値を部分集合として含む。log(w) の主値を Log(w) とし、m, n を任意の整数とすると、両辺の取り得る値は
- 等式 (bc)x = bx⋅cx および (b/c)x = bx/cx は x が実数でさらに b と c が正の実数ならば成り立つ。しかし主枝を用いた計算で
および
が反例として示される。
他方、x が整数のときには任意の非零複素数に対して成り立つ。
複素数冪を多価函数として考えれば、((−1)(−1))1/2 の取り得る値は {1, −1} で、等式は成り立つが {1} = {((−1)(−1))1/2} と言うことは間違っている。 - 等式 (ex)y = exy は x と y が実数であるときには成り立つが、任意の複素数に対して正しいと仮定すると、Clausen et al. (1827)[15]の発見した任意の整数 n に対して、
という不合理が生じる。この推論にはいくつも問題がある:
- 主な誤りは、二行目から三行目に行くときに冪の順番を変えることで選ばれる主値が変わることである。
- 多価函数の視点から見ると、最初の誤りは更に早く起きている。一行目で暗に e は実数としているにも拘らず、e1+2πin の結果は複素数であり、e + 0i と書いたほうがよい。二行目を実数ではなくこの複素数で置き換えることで、そこでの冪が取れる値を複数持つようになる。二行目から三行目で指数の順番を変えたことも、取りうる値の数に影響を及ぼす。(ez)w ≠ ezw だが、整数 n にわたって多価な意味で (ez)w = e(z+2πin)w としたほうがよい。
一般化
モノイドにおける冪
冪演算は任意のモノイドにおいて定義できる[16]。モノイドは単位元を持つ半群、すなわち適当な集合 X を台として合成あるいは乗法と呼ばれる二項演算が定義される代数系であって、その乗法が結合法則を満足し、かつ乗法単位元 1X を持つものを言う。モノイドにおける自然数冪は
として帰納的に定義することができる(先の式の右辺(の 1)は X の単位元、後の式の左辺の 1 は自然数の 1 で、当然だがこれらは互いに別のものである)。特に先の式(零乗すること)は「単位元を持つ」ことによって初めて意味を成す規約であることに注意すべきである(空積も参照のこと)。
モノイドの例には群や環(の乗法モノイド)のような数学的に重要な多くの構造が含まれ、またより特定の例として行列環や体の場合について後述する。
行列および線型作用素の冪
正方行列 A に対して A 自身の n 個の積を行列の冪と呼ぶ。また A0 は単位行列に等しいものと定義され[17]、さらに A が可逆ならば A−n ≔ (A−1)n と定義する。
行列の冪は離散力学系の文脈でしばしば現れる。そこでは行列 A は適当な系の状態ベクトル x を次の状態 Ax へ遷移させることを表す[18]。これは例えばマルコフ連鎖の標準的な解釈である。これにより、A2x は二段階後の系の状態であり、以下同様に Anx は n 段階後の系の状態と理解される。つまり行列の冪 An は現在と n 段階後の状態の間の遷移行列であって、行列の冪を計算することはこの力学系の発展を解くことに等しい。便宜上、多くの場合において行列の冪は固有値と固有ベクトルを用いて計算することができる。
行列を離れてより一般の線型作用素にも冪演算は定められる。例えば微分積分学における微分演算 d / dx は函数 f に作用して別の函数 df / dx = f' を与える線型作用素であり、この作用素の n-乗は n-階微分
である。これは線型作用素の離散的な冪の例であるが、作用素の連続的な冪が定義できたほうがよい場面が多く存在する。C0-半群の数学的理論はこのような事情を出発点としている[19]。離散冪指数に対する行列の冪の計算が離散力学系を解くことであったのと同様に、連続冪指数に対する作用素の冪の計算は連続力学系を解くことに等しい。そういった例として熱方程式、シュレーディンガー方程式、波動方程式あるいはもっとほかの時間発展を含む偏微分方程式を挙げることができる。このような冪演算の特別の場合として、微分演算の非整数乗は分数階微分と呼ばれ、分数階積分とともに、分数階微分積分学の基本演算の一つとなっている。
有限体における冪
体は、四則演算が矛盾なく定義されそれらの馴染み深い性質が満足されるような代数的構造である。例えば実数全体は体を成す。複素数の全体、有理数の全体などもそうである。これら馴染み深い例が全て無限集合であるのと異なり、有限個の元しか持たない体も存在する。そのもっとも簡単な例が二元体 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 がただ一つ存在して、任意の x ∈ F に対して px = 0 が成り立つ(x を p 個加えれば零になる)という性質を持つ。例えば二元体 F2 では p = 2 である。この素数 p はその体の標数と呼ばれる。F を標数 p の体として F の各元を p-乗する写像 f(x) = xp を考える。これは F のフロベニュース自己準同型と呼ばれる。新入生の夢(幼稚な二項定理)とも呼ばれる等式 (x + y)p = xp + yp がこの体においては成り立つため、フロベニュース自己準同型が実際に体の自己準同型を与えるものであることが確認できる。フロベニュース自己準同型は F の素体上のガロワ群の生成元であるため数論において重要である。
抽象代数学における冪
冪指数が整数であるような冪演算は抽象代数学における極めて一般の構造に対して定義することができる。
とするとき、任意の x ∈ X と任意の自然数 n に対して冪 xn は、x の n 個のコピーの積を表すものとして
のように帰納的に定義される。これは以下のような性質
を満足する。さらに、考えている演算が両側単位元 1 を持つ:
ならば x0 は任意の x に対して 1 に等しいものと定義する。[要出典]
さらにまた演算が両側逆元を持ち、なおかつ結合的
ならばマグマ X は群を成す。このとき x の逆元を x−1 と書けば、冪演算に関する通常の規則
はすべて満足される。また(例えばアーベル群のように)乗法演算が可換ならば
も満足される。(アーベル群が通常そうであるように)二項演算を加法的に書くならば、「冪演算は累乗(反復乗法)である」という主張は「乗法は累加(反復加法)である」という主張に引き写され、各指数法則は対応する乗法法則に引き写される。
一つの集合上に複数の冪結合的に項演算が定義されるときには、各演算に関して反復による冪演算を考えることができるから、どれに関する冪かを明示するために上付き添字に反復したい演算を表す記号を併置する方法がよく用いられる。つまり演算 ∗ および # が定義されるとき、x∗n と書けば 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) は i を ai へ送る写像を表す)。
無限基数 κ と集合 A に対しても、記号 Aκ は濃度 κ の集合から A への写像全体の成す集合を表すのに用いられる。基数の冪との区別のために κA と書くこともある。
反復直和
一般化された冪は、複数の集合上で定義される演算や追加の構造を持つ集合に対しても定義することができる。例えば、線型代数学において勝手な添字集合上でのベクトル空間の直和を考えることができる。つまり Vi をベクトル空間として
を考えるとき、任意の i について Vi = V とすれば得られる直和を冪記法を用いて V⊕N あるいは直和の意味であることが明らかならば単に VN のように書くことができる。ここで再び集合 N を基数 n で取り替えれば Vn を得る(濃度 n を持つ特定の標準的な集合を選ぶことなしに、これは同型を除いてのみ定義される)。V として実数体 R を(それ自身の上のベクトル空間と見て)とれば、n を適当な自然数として線型代数学でもっともよく調べられる実ベクトル空間 Rn を得る。
配置集合
冪演算の底を集合とするとき、何も断りがなければ冪演算はデカルト積である。複数の集合のデカルト積は n-組を与え、n-組は適当な濃度を持つ集合上で定義された写像として表すことができるのだから、この場合冪 SN は単に N から S への写像全体の成す集合
である。この定義は |SN| = |S||N| が満たされるという意味で基数の冪と整合する。ただし |X| は X の濃度を表す。"2" を集合 {0, 1} として定義すれば |2X| = 2|X| が得られる。ここに 2X は X の冪集合であり、普通は 𝒫(X) などで表される。
圏論における冪対象
デカルト閉圏において、任意の対象に対して別の任意の対象を冪指数とする冪演算を冪対象によって与えることができる。集合の圏における冪対象は配置集合であるから、これはその一般化になっている。考えている圏に始対象 0 が存在するならば、冪対象 00 は任意の終対象 1 に同型である。
順序数・基数の冪
基数 κ, λ に対して冪 κλ は基数 λ の任意の集合から基数 κ の任意の集合への写像全体の成す集合の基数を表す[20]。κ, λ がともに有限ならばこれは通常の算術的な(つまり自然数の)冪演算と一致する(たとえば、二元集合から元を取って得られる三つ組全体の成す集合の基数は 8 = 23 で与えられる)。基数の算術において κ0 は常に(特に κ が無限基数や 0 であるときでさえ)1 である。
基数の冪は順序数の冪とは異なる。後者は超限帰納法を含む過程の極限として定義される。
反復冪
自然数冪が乗法の反復として考えられたことと同様に、冪演算を繰り返す演算というものを定義することもできる。それをまた反復すれば別の演算が定義され、同様に繰り返してハイパー演算の概念を得る。このようにして得られるハイパー演算の列において、次の演算は前の演算に対して急速に増大する。
写像の冪の記法に関する注意
合成冪
写像の冪乗となるべきものとして、写像を表す符牒の直後に整数の上付き添字を添えたとき、それは(反復乗法ではなくて)反復合成冪の意味で用いることがよく行われる。つまり例えば f3(x) は f(f(f(x))) の意味であり、また特に f−1(x) は f の逆写像を意味するのが普通である。反復合成写像はフラクタルや力学系の研究において興味を持たれる。チャールズ・バベッジは写像の平方根 f 1/2(x) を求める問題を研究した最初の人であった。
値ごとの冪
しかし歴史的経緯により、三角函数の場合には、函数の略号に正の冪指数を添えたときは函数の値に対して冪を取ることを意味する一方で、−1 を冪指数としたときは逆函数を意味するという特別な文法が適用される。つまり、 sin2 x は (sin x)2 を括弧を用いずに略記する方法に過ぎない一方、sin−1 x は逆正弦函数 arcsin x を意味するのである。三角函数の逆数函数は(例えば 1/(sin x) = (sin x)−1 = csc x のように)それぞれ固有の名前と略号が与えられているから、三角函数の逆数の略記法は無用である。同様の規約は対数函数にも適用され、log2 x はふつう (log x)2 の意味であって log log x の意味でない。
上付き添字
添字付けられた変数を考えるとき、その変数の添字を上付きにする場合があり、それはあたかも冪であるかのような印象を受けるかもしれないが混同するべきではない。これは特にテンソル解析においてベクトル場の座標表示などで現れる。あるいはまた数列の列のような、既にそれ自身添字付けられているような量に対してさらに添字付けを行う場合にもしばしば用いられる。
高階導函数
効率的な演算法
コンピュータ上で指数を自然数とする冪乗(累乗)を効率よく行う演算方法としてバイナリ法(二進数法; en:exponentiation by squaring) とも呼ばれる演算方法を示す。
RSA暗号や確率的素数判定法であるフェルマーテストなどでは、巨大な自然数を指数とする累乗を行う。この方法を使うと、指数がいかに巨大であっても高々そのビット数の2倍の回数の乗算で算出することが可能になり、繰り返し掛けるよりも大幅に効率がよくなる。特にRSA暗号やフェルマーテストなどにおいて各演算後に必要となる剰余演算(一般に最も計算時間がかかる)の回数を減らす効果がある。
一般に、コンピュータにとって標準的な(32ビットコンピュータならば約4億までの)自然数や浮動小数点数を底とする場合は下位桁から計算する方式を、前述のような巨大な自然数を底とする場合には上位桁から計算する方式を用いると効率が良い。
下位桁から計算する方式
バイナリ法では、次の性質を利用する。
例えば (a8)2 = a16 である。したがって、a(すなわち a1)から始めて2乗を繰り返すと次行のとおりになる。
これらの数のうち、適切なものを選んで掛け合わせれば、任意の累乗を速く(すなわち少ない乗算回数で)計算することができる[21]。例えば a43 は、指数法則によって、
として計算することができる。乗算回数は 8 回[注釈 3]で済むので、a を 42 回繰り返し掛け合わせるのに比べて効率が良い。(下図で「→」は乗算を表し、「⇒」は2乗を表す。)
(十進表記): | a1 | a2 | a4 | a8 | a16 | a32 | ||||||
2乗の繰返し(二進表記): | a1 | ⇒ | a10 | ⇒ | a100 | ⇒ | a1000 | ⇒ | a10000 | ⇒ | a100000 | |
↓ | ↓ | ↓ | ↓ | |||||||||
累乗の計算(二進表記): | a1 | → | a11 | ─ | ── | → | a1011 | ─ | ─── | → | a101011 | |
(十進表記): | a1 | a3 | a11 | a43 |
- 指数を n とし、2乗していく値 p := a、結果値 v := 1 とする。
- n が 0 なら、v を出力して終了する。
- n の最下位桁が 1 なら、v := v * p とする。
- n := [n/2] とし(端数切捨て)、 p := p * p として、2. に戻る。
整数の内部表現が二進法であるコンピュータなら、4. では除算の代わりにシフト演算を用いることができる。
この方式は a が浮動小数点数である場合や、最終結果がレジスタに収まることがわかっている場合に効率が良い。また乗算にモンゴメリ乗算などを用いて冪剰余を計算する場合も、この方式で充分な効率が得られる。
上位桁から計算する方式
上の方式と同様に、次の性質を使う。
これに性質 を組み合わせると、次の関係が成り立つ。
指数が偶数か奇数かによってこれら二つの式を使い分け、指数を順次約1/2にしていくことができる。例えば は、
である。そして も同様に、
である。 はこうなる。
以下同様に、こうなる。
これを逆順にたどり、
として算出できる[注釈 4]。(下図で「→」は乗算を表し、「⇒」は2乗を表す。)
a | a | a | ||||||||||||||||
↓ | ↓ | ↓ | ||||||||||||||||
二進表記: | a1 | ⇒ | a10 | ⇒ | a100 | → | a101 | ⇒ | a1010 | ⇒ | a10100 | → | a10101 | ⇒ | a101010 | → | a101011 | |
十進表記: | a1 | a2 | a4 | a5 | a10 | a20 | a21 | a42 | a43 |
2乗した後に a を乗算するか否かは、指数 n を二進表記したときの各ビットが1であるか否かと一致する。
コンピュータのアルゴリズムとして書くとこうなる。
- 指数 n の二進表記を 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 なら 3. に戻る。
この方式では、4. における乗数が常に a なので、下位桁から計算する方式に比べて乗数の桁数が小さくなり、計算時間がかからない。これは特に、レジスタに入りきらないような巨大な自然数を扱う場合に顕著となる。ただし(RSA暗号のように)冪乗の剰余を計算する場合であって法の大きさが a と同程度ならば、この効果はない。
また 4. における乗数が常に a なので、あらかじめ a が定数(2 や 10 など、またはディフィー・ヘルマン鍵共有の生成元 g など)であることがわかっている場合には、4. の乗算を最適化をすることができる。
巨大な自然数の汎用的な冪算ルーチン(a が小さい可能性が高い)や、a が小さかったり定数であることがわかっている場合、冪乗の剰余を計算する場合であってモンゴメリー演算を用いず別途剰余を計算する場合、数を保持するコストが高い場合など、指数を二進表記するコスト以上の効率が得られる場合に選択される。
脚注
参考文献
関連文献
関連項目
外部リンク
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.