[ ホーム ] [ 加算 ] [ 減算 ] [ 乗算 ] [ 除算 ]

上へ

四則演算/除算

配列除算
最終更新日：2007/04/26　新規

●概要

　この除算では、ネイティブな除算命令は使用できなく、引き算とシフトで行う。バイナリーではないので、本来のシフト命令ではなく、10進の乗除算で行う。被除数から除数を何回引けるかを演算することになるので、時間が掛かる。部分商は10進1桁となる。

●基本原理

　原理は簡単である。A を被除数、B を除数、Q を部分商とすれば、概念は、

While A > 0
   Q = 0
   While A > B             'ここは平均 5 回のループとなる
      A = A - B
      Q = Q + 1
   End While
   Q を所定の桁位置に格納
   A = A * 10
End While

となる。これは、10進1桁の部分商を割切れるまで求め続けるものとなっている。実際には、精度桁を設定し、それに達しても終了するようにする。A、B を仮数部配列とすれば、配列除算となる。

●仮商方式

○原理

　何回引けるかの演算が時間の掛かる処理となる。今、A と B 配列の先頭要素の整数商を、

  Qp = A(0) \ B(0)

とすれば、Qp は、真値に近い予測値となる。これを、

　Qp * B ≦ A ?

と検算し、Qp ＞ 0 でかつ上式が成立すれば、Qp は、真値となる。Qp * B の演算は、配列*Integer で速い。不成立なら、Q = Qp - 1 となる。例えば、下図では、

Qp = 23456789 \ 12345678 = 1 となり、条件は成立する。下図は、不成立の例である。

Qp = 50000000 \ 10000000 = 5 であるが、Qp * B = 50000000 00000000 00000015 となり、A より大きくなる。この場合は、Q = 5 - 1 = 4 とすれば良い。

　Qp のとり得る範囲は、0 〜 10 となる。10 になる場合は、先頭が等しく、後ろは、B が大きい場合に起こる。下図のような例である。始めのQpは 1 となるが、直ぐに 0 に補正される。次の商では、Aが10倍されているので、Qp = 5|00000000 \ 50000000 = 10 となる。しかし、この10は、9に補正される。

○仮商アルゴリズム

  1. もし、 A(0) ≧ B(0)  であれば、

  2. Q = A(0) \ B(0) とし、A と、Q * B 比較し、
    ・ ＞ であれば、Q を正解
    ・ ＝ であれば、Q を正解とし、終了とする
    ・ ＜ であれば、Q = Q - 1 とする

  3. A = A - Q * B とし、A を10倍する(シフトアップする)

  4. 次の商に行く

○高速化アルゴリズム

　Q * B の乗算は、Q = 1 〜 10 までで、また、B はその除算中不変であるから、Q * B は、変数ではなく、その除算中は定数と言える。 高々10個なので、除算開始時に予め算出し、テーブル化しておけば、QB(Q) = Q * B と参照できる。除算中に圧倒的に多い、Q * B 乗算がなくなるので、高速化が期待できる。

 QB() は、予め生成された Q * B のテーブル

  1. もし、 A(0) ≧ B(0)  であれば、

  2. Q = A(0) \ B(0) とし、A と、QB(Q) 比較し、
    ・ ＞ であれば、Q を正解
    ・ ＝ であれば、Q を正解とし、終了とする
    ・ ＜ であれば、Q = Q - 1 とする

  3. Q ＞ 0 ならば、A = A - QB(Q) とする。

  4. A を10倍する(シフトアップする)

  5. 次の商に行く。ループアップまたは、A = 0 であれば終了。

・QB() テーブルの生成

　以下のようにすれば良い。累算により、乗算をなくしている。

NumB は、B の配列
NumQ は、バッファ、初期値0
QB は、Q * B のテーブル

Dim QB() As Array      '配列の配列

ReDim QB(10)
For i = 1 To 10
   AddNumD(NumQ, NumB, NumQ)     ' 専用関数でB++ の演算(累算)
   QB(i) = NumQ.Clone
　'→NumQは、使い回ししているので、Clone としないと、QB(i)は全て同じ値になってしまう。 　　　　
Next