[ ホーム ] [ TIPS ウィンドウズ系 ] [ TIPS グラフィックス系 ] [ TIPS メルチメディア系 ] [ TIPS 理数系 ] [ TIPS 総覧 ]

上へ
S0001 数式処理
S0002 数式演算
S0003 陰関数のグラフ
S0004 モンテカルロ法
S0005 最小自乗法
S0006 高速冪乗算
S0007 正規乱数
S0008 相関係数
S0101 高速ソート
S0102 高速検索

●解説

　ソフトウェア実験室で既に紹介している冪乗演算の速度比較では、整数冪数の場合は、演算子＾よりも直接の乗算*の方が高速であることを示している。しかし、冪数が比較的小さい時の話で、大きくなると、＾の方が速くなる。これは、＾は冪数に依らず、ほぼ同じ速度で演算できるからである。しかし、＾演算は、整数演算ではなく、精度が保てないので、*演算は場合によっては必要となる。

　ここでは、整数冪数の冪乗演算を直接*を用いながら高速化する方法を紹介する。

●原理

指数法則を上手く利用する。つまり、

　　A^N  =  A^a0･A^a1･A^a2･･････A^ak

 但し、�蚤i = N

である。ここで、ai=1 とすれば、真っ向勝負な方法となる。

ところで、一般に整数Nは、二進法で表せば、

　　N = a0･2⁰ + a1･2¹ + a2･2² + ・・・・

である。ai は、0 か1 である。つまり、

　　A^N = A^a0･1 ･ A^a1･2 ･ A^a2･4  ・・・・

と表せる。例えば、A²⁵は、

　　A²⁵ = A¹･A⁸･A¹⁶

などである。この例で、

　　A⁸ = A⁴・A⁴

　　A⁴ = A²・A²

などであるから、4は2から、8は4からそれぞれ、一回の乗算で得られる。この方法では、6回の乗算で演算できることになる。真っ向法では、24回必要。一般に、この方法では、平均乗算回数は、 二進桁数 - 1 と ビットが 1 の数の合計となる。ビットが 1 の数は平均二進桁数の半分とすれば、

   M = log₂N - 1 +  (log₂N) / 2
      = (3 / 2) * (log₂N) - 1 

となる。

　N = 32768 とすれば、回数は、29回となる。真っ向法では、32767回なので、およそ、1000倍速くなる。二進で全ビットがオンの場合(2^M - 1)が最遅となる。

●方法

　冪数Nの2ⁱのビットを、i=0 から検査し、まず、A²ⁱを以前の値を自乗して求めておき、ビットが1なら、経過値Bに乗じておく。B = B * A²ⁱである。これを繰り返す。

●実例

実数の冪乗算　D^P

Dim P As Integer
Dim UP As UInteger       '指数のシフト用
Dim D, DD, W As Double
DD = 途中の経過値
D = 冪乗される数
P = 冪数

DD = 1     'D⁰
W = D
UP = P
Do
   If (UP And 1) = 1 Then DD = DD * W  
   UP = UP >> 1                      'シフト命令で1/2する
   If CInt(UP) = 0 Then Exit Do
   W = W * W
Loop
　

●事例

 1.0001¹⁰⁰⁰⁰

の計算を、Pow関数、*、*高速法の演算時間を測定した。