|
レガシ四則算 |
|
除算：高速部分商 |
| 最終更新日：2006/04/17 |
●当初の問題点
遅いのが問題であるが、その原因は、シフト＆減算をまともに行っていることにある。この除算の演算時間は、基数に関係なく、精度の桁数で決まるので、影響は大きい。現在、ある桁の商 Q は、
Q = 0
While A > B
A = A - B
Q = Q + 1
End While
のように、アルゴリズムそのままとなっている。このWhileのループ回数は、最小0、最大9で、平均は5となる。精度3万桁の商では、平均15万回のループとなる。つまり、15万回の多倍長比較と15万回の減算を行っている。
●仮の商方式
一般的な手法として、多倍長を表す配列の先頭要素にて、商の予測を行うものがある。求まった仮の商を、後で検算し、補正すると言うものである。
例えば、今、上図のような二つの多倍長A、B があると、その最初の商は、仮に、
Q = A(0) \ B(0)
= 23456789 \ 12345678
= 1
とできる。この商Q にて、
A > Q * B ?
を検算するのである。このとき、True であれば、Q は正しく、False であれば、Q = Q - 1 と補正する。うまく行けば、多倍長比較、多倍長減算、多倍長XInteger乗算がそれぞれ1回で商1桁が求まる。 A(0) \ B(0) の演算時間はこの際無視できる。Falseとなるのは、例えば、下図のような場合である。仮の商は 5 となるが、実際には、4 が正しい。
Qは、0 から 10 までとなる。10 になる場合は、先頭が等しく、後ろは、B が大きい場合に起こる。下図のような例である。始めのQは1となるが、直ぐに0に補正される。次の商では、Aが10倍されているので、Q = 500000000 \ 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 * B は、多倍長XInteger(10進1桁)の乗算で極めて速く演算できる。しかし、求める商の精度桁数 * (Bの配列サイズ) のネイティブ乗算が必要となる。例えば、3万桁の商で、8千桁のBとすれば、3万*1000 で、3千万回の乗算となる。
ところで、除算中、Aは、シフトされ減算され、刻々と変化するが、B は、ズッとそのままである。従って、B * Q は、 Q = 1 to 10 で、高々10種類の多倍長数値である。これを、毎回計算するのは無駄で、一度計算したものを再利用すれば、乗算数が激減する。メモリが少し潤沢である前提で、Q * B を予め計算し、テーブル化する。この時、乗算ではなく、累算で求められる。つまり、乗算は0回となる。
.NET では、配列そのものを、配列の要素にできるので、Q * B テーブルも以下の例のようにしている。
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
これにて、QB(Q) は、Q * B の値(配列)を示す。配列の要素は、QB(Q)(k) となる。
QBでは、最初は無とし、新しいQが求まった時点で初めて、QB(Q) を生成する方法もあるが、商の桁数が大きい場合は、確率的に全ての値(0〜9)が生起されるので、最初に一気に生成しても、時間はほぼ同じと言える。桁数が小さい場合に不利にはなるが。
●改良アルゴリズム
-
もし、 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 であれば終了。
●結果
実際に改良し、以下のような結果となった。テストに使用した数値は乱数であり、商は無限小数になっているので、割り切れている場合はない(はず)。
桁数の大きい部分では概ね、元の55%前後の時間となった。予測通り、桁数が小さい部分は、効果がない、もしくは小さくなっている。