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

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

レガシ四則算

除算:高速シフトアップ

最終更新日:2006/04/17

●シフトアップの問題点

 シフトアップの演算を分析すると、乗算、加算、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より随分短くなった。