冪乗
写像の冪乗となるべきものとして、写像を表す符牒の直後に整数の上付き添字を添えたとき、それは(反復乗法ではなくて)反復合成冪の意味で用いることがよく行われる。つまり例えば 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 の意味でない。
添字付けられた変数を考えるとき、その変数の添字を上付きにする場合があり、それはあたかも冪であるかのような印象を受けるかもしれないが混同するべきではない。これは特にテンソル解析においてベクトル場の座標表示などで現れる。あるいはまた数列の列のような、既にそれ自身添字付けられているような量に対してさらに添字付けを行う場合にもしばしば用いられる。
函数 f の n-階導函数はふつう f(n) と書かれるように、冪記法は冪指数を括弧で囲んで書くこともある。
コンピュータ上で指数を自然数とする冪乗(累乗)を効率よく行う演算方法としてバイナリ法(二進数法; exponentiation by squaring) とも呼ばれる演算方法を示す。
RSA暗号や確率的素数判定法であるフェルマーテストなどでは、巨大な自然数を指数とする累乗を行う。この方法を使うと、指数がいかに巨大であっても高々そのビット数の2倍の回数の乗算で算出することが可能になり、繰り返し掛けるよりも大幅に効率がよくなる。特にRSA暗号やフェルマーテストなどにおいて各演算後に必要となる剰余演算(一般に最も計算時間がかかる)の回数を減らす効果がある。
一般に、コンピュータにとって標準的な(32ビットコンピュータならば約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
これらの数のうち、適切なものを選んで掛け合わせれば、任意の累乗を速く(すなわち少ない乗算回数で)計算することができる。例えば a43 は、指数法則によって、
a^{43} = a^{32+8+2+1} = a^{32} \times a^8 \times a^2 \times a^1
として計算することができる。乗算回数は 8 回 ((((a^2)^2)^2)^2)^2 を計算するのに 5 回、a^1 \times a^2 \times a^8 \times a^{32} に 3 回の、合計 8 回かかる。で済むので、a を 42 回繰り返し掛け合わせるのに比べて効率が良い。(下図で「→」は乗算を表し、「⇒」は2乗を表す。)
コンピュータのアルゴリズムとして書くとこうなる。
指数を n とし、2乗していく値 p := a、結果値 v := 1 とする。
n が 0 なら、v を出力して終了する。
n の最下位桁が 1 なら、v := v * p とする。
n := [n/2] とし(端数切捨て)、 p := p * p として、2. に戻る。
整数の内部表現が二進法であるコンピュータなら、4. では除算の代わりにシフト演算を用いることができる。
この方式は 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
として算出できるこの場合の乗算回数も、下位桁から計算するのと同じく合計 8 回かかる。。(下図で「→」は乗算を表し、「⇒」は2乗を表す。)
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 が小さかったり定数であることがわかっている場合、冪乗の剰余を計算する場合であってモンゴメリー演算を用いず別途剰余を計算する場合、数を保持するコストが高い場合など、指数を二進表記するコスト以上の効率が得られる場合に選択される。