下位桁から計算する方式
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/03/14 00:51 UTC 版)
バイナリ法では、次の性質を利用する。 ( a x ) 2 = a 2 x {\displaystyle (a^{x})^{2}=a^{2x}} 例えば (a8)2 = a16 である。したがって、a（すなわち a1）から始めて2乗を繰り返すと次行のとおりになる。 a 1 → a 2 → a 4 → a 8 → a 16 → a 32 → ⋯ {\displaystyle 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 × a 8 × a 2 × a 1 {\displaystyle a^{43}=a^{32+8+2+1}=a^{32}\times a^{8}\times a^{2}\times a^{1}} として計算することができる。乗算回数は 8 回で済むので、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 が浮動小数点数である場合や、最終結果がレジスタに収まることがわかっている場合に効率が良い。また乗算にモンゴメリ乗算などを用いて冪剰余を計算する場合も、この方式で充分な効率が得られる。
※この「下位桁から計算する方式」の解説は、「冪乗」の解説の一部です。
「下位桁から計算する方式」を含む「冪乗」の記事については、「冪乗」の概要を参照ください。
- 下位桁から計算する方式のページへのリンク
