[ ホーム ] [ PC技術/システム技術 ] [ VB.NETプログラミング ] [ なるほどナレッジ ] [ インフォメーション ]

上へ
高速部分商
高速シフトアップ

●シフトアップの問題点

　シフトアップの演算を分析すると、乗算、加算、Mod、\ からなっている。これを筆者所有マシンのCPU演算速度にすると、6 + 1 + 30 + 30 = 67ns となる。圧倒的にMod、\ が支配している。ちなみに、このシフトアップの演算数は、被乗数の配列サイズ X 精度桁数 となり、桁数の自乗に比例する部分となり、バカにならない部分である。

　Mod、\ 演算を回避すれば、更に高速化できる。

●10倍するだけに注目

　配列要素の単位の演算で、基数未満の値を10倍するだけと言うことは、

• 演算結果は、Integer以内である。また、10億以上になることはない。
  ∴ 最悪値は、99999999 * 10 + 9 = 999999999

• キャリーする値は、0億から9億までの10種類である。

• キャリー が分かれば、残る値は、引き算で求まる。

と言える。これを踏まえると、現在行っている、キャリーを求める演算は、テーブル参照に置き換えられ、演算￥ を回避できる。テーブル参照は平均5回のループとなる。

●改良版

　以下のようにした。乗算は、全Integer化し、キャリーテーブルを用意。上位要素が使用するキャリー値もテーブル(CUT)にすることで、\ をなくせる。

CT() As Integer = {0, 100000000, 200000000, 300000000, 400000000, 500000000, 600000000, 700000000, 800000000, 900000000, 1000000000}
CUT() As Integer = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}

V = 10
CU = 0
For i = L - 1 To 0 Step -1
   M = N(i) * V + CU
   For j = 1 To 10
      If M < CT(j) Then
         CUV = CT(j - 1)       'キャリーされる値
         CU = CUT(j - 1)       '上位で使用されるキャリー値
         Exit For
      End If
   Next
   N(i) = M - CUV                  '従来、M Mod Base としていた部分
Next

この処理の演算は、乗算、加算、比較、代入、減算 となり、6 + 1 + 1+ 1+ 1 + 5 * 2 = 20 ns となる。改良前の67より随分短くなった。