2進数の高速除算アルゴリズム

Question

現在、Logisim（つまり論理ゲートのみ）を使用して16ビットALUを構築しており、除算プロセスに固執しています。 （下図のように）私は現在、単なる標準の「分割アルゴリズムループ」を使用しています：

1. 入力値を読みます。
2. 入力値を比較してください。比較処理が完了するまで待つ。
3. もしA < Bがステップ10に行くならば、A ≥ Bならば、次のステップに進みます。
4. AからBを減算する。
5. 減算処理が完了するまで待ちます。
6. 1を加算してカウントします。
7. カウント処理が完了するまで待ちます。
8. 減算プロセスからの値を入力に書き込みます。
9. 手順1に進みます。
10. 回答はカウント余り

これは、しかし、大規模な答えとプロセスのための非常に長い時間を（65,000回を300ダニサイクルを繰り返すことは楽しみではありません）かかります。 論理ゲートを使用して実装できるより速い（それだけで、加算および/または減算および/または乗算およびブール論理を使用する）類似のアルゴリズムがあるかどうかは疑問です。 ヘルプやアイデアをいただければ幸いです！ フレーザー

Answer 1

long-divisionを使用してください。バイナリでは、各ビット位置の商は1または0しかないので、乗算はありません。したがって、条件付き減算（結果が負でない場合は減算）およびシフトとして実装できます。

もちろん、これは単なる概要です。

Answer 2

32/16：16 + 16除算の一般的な方法は、16ビットレジスタのペア（演算中に更新される）と除数を自身のレジスタに格納することですt）。 16回、除数から被除数の上位17ビットを減算する。借りが結果になった場合は、結果を破棄し、除数を1つだけ左にシフトし、lsbに0を入れます。借り結果がない場合は、結果を除数に格納したまま左にシフトして格納しますが、lsbには1を入れます。 16のこのようなステップの後、被除数レジスタの下位16ビットは商を保持し、上位16ビットは余りを保持する。この演算は、商が16ビットで表現可能である場合にのみ機能することに注意してください。また、このように32/16：16 + 16除算を実装するプロセッサでは、各ステップの被除数の上位16ビットが16ビットの16ビットである必要があるため、任意に大きな数値を16ビットの数で分けてもよい。前のステップ。