|
四則演算/除算 |
|
配列除算 |
| 最終更新日：2006/11/29 新規 |
●概要
この除算では、ネイティブな除算命令は使用できなく、引き算とシフトで行う。バイナリーではないので、本来のシフト命令ではなく、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に補正される。
○仮商アルゴリズム
-
もし、 A(0) ≧ B(0) であれば、
-
Q = A(0) \ B(0) とし、A と、Q * B 比較し、
・ ＞ であれば、Q を正解
・ ＝ であれば、Q を正解とし、終了とする
・ ＜ であれば、Q = Q - 1 とする -
A = A - Q * B とし、A を10倍する(シフトアップする)
-
次の商に行く
○高速化アルゴリズム
Q * B の乗算は、Q = 1 〜 10 までで、また、B はその除算中不変であるから、Q * B は、変数ではなく、その除算中は定数と言える。 高々10個なので、除算開始時に予め算出し、テーブル化しておけば、QB(Q) = Q * B と参照できる。除算中に圧倒的に多い、Q * B 乗算がなくなるので、高速化が期待できる。
QB() は、予め生成された Q * B のテーブル
-
もし、 A(0) ≧ B(0) であれば、
-
Q = A(0) \ B(0) とし、A と、QB(Q) 比較し、
・ ＞ であれば、Q を正解
・ ＝ であれば、Q を正解とし、終了とする
・ ＜ であれば、Q = Q - 1 とする -
Q ＞ 0 ならば、A = A - QB(Q) とする。
-
A を10倍する(シフトアップする)
-
次の商に行く。ループアップまたは、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