Chapter Sixteen

第16話


四則演算の最後となった除算VIについて説明しよう。

考え方として簡単なのは引き算を繰り返す方法だが、計算時間は繰り返しの回数(被除数と除数の比)に比例する。筆算方式の場合の計算時間は被除数と除数の桁数の差にだいたい比例するだろう。だから、VIをつくる手間はかかるが筆算の方法を選んだ方が良さそうだ。

そのための準備として、桁上げVIを作ることにした。U32n;Aをビット列と考えたとき、左シフトを繰り返し最大ビットが１になるようにするVIだ。

シンプルな考え方は、最大ビットが１になるまで左シフトを繰り返す方法だ。（Shift0.vi）
(注　shiftの前の-1はバグで削除しないといけない）

しかし、ビット列の先頭から０がたくさん続くときは、いっきにシフトした方が速そうだ。U32単位で、０がどこまで続くか調べて事前にシフトする方法を試してみよう。（Shift1.vi）

スレッショルド関数は遅いかもしれないから、Whileで回した方が速いかもしれない。（Shift2.vi）
(注　shiftの前の-1はバグで削除しないといけない）

さあ、３つの方法を考えたが、どれが一番速いのだろうか？LV4のプロファイルで調べてみよう。

配列の上半分が０でそれ以下がランダムなU32nの時の動作時間
InstrName
DS
VI
SubVIs
Total
n runs
avg
Shift0.vi
0
0.5743
0.0000
0.5743
100
0.0057
Shift1.vi
0
0.0343
0.0000
0.0343
100
0.0003
Shift2.vi
0
0.0419
0.0000
0.0419
100
0.0004

配列の全体がランダムなU32nの時の動作時間
InstrName
DS
VI
SubVIs
Total
n runs
avg
Shift0.vi
0
0.0306
0.0000
0.0306
100
0.0003
Shift1.vi
0
0.0361
0.0000
0.0361
100
0.0004
Shift2.vi
0
0.0501
0.0000
0.0501
100
0.0005

このテストからShift1.viの方法が安定して速いことが分かったが、調べると入力の配列の要素が１の時にシフト数が変になるので、Shift2.viを使うことにした。標準のわり算の配置に合わせてフロントパネルに要素を配置した。


（注　Shift2.viに変更する前のダイアグラム）
画面をスクロールしないと全体が見えない人が多いと思うが、残念ながらこれでもダイアグラムを小さくしようと努力した結果だ。
大部分は大きなケース構造の中にはいっているがFalseは簡単なので図は省略した。ダイアグラムの始めで、AとBの大小判定を行ってBの方が大きいとき(False)には、商は0、余りがAで出力される。
Trueの場合が本題となる。

（１）A,Bともに先頭のビットが１となるようにShift1.viで左シフトを行う。A',B'としよう。
（２）左シフトした数をn_a,N_bとすると等しいか、n_bの方が大きくなり、(n_b) - (n_a) + 1の回数だけ筆算式のわり算（Forループの中のダイアグラム）を行えばよい。
（３-１）A' - B' を行い、ボローが出ないときには商を記録するU32n（０に初期化）のLSBをTにする。A'にA' - B' を１回左シフトして入れる。
（３-２）A' - B' を行い、ボローが出たときには商を記録するU32nのLSBをFにする。B'にB' を１回右シフトして入れる。
（４）余りは、N_bから（３-２）で右シフトした回数を引いた数だけ、右シフトする。

以上が大まかな計算の流れだ。これを書きながらバグチェックをしている状態だから、もっと頭が整理できれば簡単になりそうな気もするのだが、、、
とりあえず、実質的に無制限の大きさの整数演算の四則演算ができあがったことになる。

See you!

Nigel Yamaguchi
戻る