マイクロコンピュータ 乗算演算について

質問

マイクロコンピュータで、８ビット演算回路の乗算演算を行ったのですが、その際、乗数の０、１パターンに応じて被乗数を左シフトさせ加算していくロジックで演算をするというアルゴリズムを組み立てて実行しました。
乗算演算をより高速化させるには、この他にどのような手段が考えられるのか教えていただけないでしょうか？
お願いいたします。

回答No.4

Tacosan

ソフトウェアでやるんだと, ほとんどどうしようもないですね.
ハードウェアでやるんだったら.... やりそうなのは部分積 (64個) を全部 AND ゲートで作っておいてあとは Carry Save Adder で Wallace木組むかなぁ?
Z80 でメモリから読み込む, というのであれば IO空間に置いておいて IN (C), A が常套手段? 1回の読み込みでは 16ビット取り出せないので 2回に分けて読み込んで ADD HL, DE を駆使するということで.

回答No.3

bloomers_daisuki

＃１，２の回答の通り、乗数と被乗数でアドレスを生成して、そのアドレスから16ビットのデータ(積)を読み込めば、非常に高速です。8ビットマイコンの話しで言えば、メモリの読み出しと等価な速度になります。ただし、256*256*2バイトのアドレスが必要になるので、レトロなZ80では実現しにくいでしょう。

もうひとつは、質問者さんの案を、全てワイヤードロジックで組むことです。

必要なロジックは、

1. シフトレジスタ
桁取りのためのシフト

2. データセレクタ
乗数のパターンで被乗数か0を出力

3. 16ビット加算器
データセレクタから出力されたデータを「一気に」加算する。

でしょうか。実際には8+2ビットの加算器が8個必要になります。
結果は、クロック無しのデータフローで出力されます。

同様に、除算回路も作成可能です。

回答No.2

rinkun

ハードウェアでやるのかソフトウェアでやるのかでも変わってきますけど、どっちかな。
8ビットだとテーブルを用意してしまって参照することも可能だね。8ビット×8ビットで64Kエントリを用意する必要があるけど。
あとは、nビット乗算はn/2ビット乗算を3回と加減算で計算できるので、これを使って再帰的に1ビットまで展開する手法もある。ただ8ビットくらいだとかえって遅くなるかもしれない。

回答No.1

DIGAMMA

こんにちは、

　「九九の表」を暗記してれば、掛け算は早いですよね。コンピュータの世界は２進法ですから「二二の表」と言うことになります。

　さて、人間が「九九の表」ではなく「０から９９」あるいは「０から９９９」までの掛け算の表を暗記していたら、計算が素早くなるのと同様にコンピュータも「二二の表」ではなく、「２５６＊２５６」の表をROMとかに記憶しておけば、理論上、８倍早くなります。

　ハードウエアで実現するなら、ありとあらゆる掛け算の結果を、予めメモリに書き込んでおくという方法をとれば、（あたりまえですが）瞬時に回答が求まります。

　ハードウエアを変えずに、ソフトのみで対処したいのならば、０から２５５までの掛け算の結果を、２５６掛ける２５６（＝６５５３６）の配列に予め定数値としてセットしたあと、１ビットづつ左シフトするのではなく、８ビットづつ左シフトするプログラムをくんでみてください。すごく早くなりますヨ。

　具体的なソースコードは自分で考えてね。

　ご参考まで。勉学がんばってください。