Schnelle Division Algorithmus für Binärzahlen

Question

Ich baue derzeit eine 16-Bit-ALU mit Logisim (dh nur Logikgatter), und bin auf einem Teilungsprozess fest. Ich bin zur Zeit nur mit dem einfachen Standard „Divisionsalgorithmus Loop“ (siehe unten):

1. Eingangswerte lesen;
2. Eingabewerte vergleichen. Warten Sie, bis der Vergleichsprozess abgeschlossen ist.
3. Wenn A < B mit Schritt 10 fortfahren. Wenn A ≥ B, mit dem nächsten Schritt fortfahren;
4. Subtrahieren Sie B von A;
5. Warten bis der Subtraktionsprozess beendet ist;
6. Fügen Sie einen hinzu, um zu zählen;
7. Warten bis der Zählvorgang beendet ist;
8. Wert vom Subtraktionsverfahren zum Eingang schreiben;
9. Weiter mit Schritt 1;
10. Antwort Auszählung Rest ist

Dies ist jedoch eine sehr lange Zeit für Prozesse mit großen Antworten nimmt (A 300 tick Zyklus 65.000 mal zu wiederholen ist nicht Spaß). Ich frage mich nur, ob es ähnliche Algorithmen gibt, die schneller sind (die ausschließlich Addition und/oder Subtraktion und/oder Multiplikation und irgendeine boolesche Logik verwenden), die unter Verwendung von Logikgattern implementiert werden könnten. Jede Hilfe oder Ideen würde sehr geschätzt werden! Fraser

Answer 1

Verwenden Sie long-division. Im binären Fall gibt es keine Multiplikation, da der Quotient an jeder Bitposition nur 1 oder 0 sein kann. Er kann also als bedingter Subtraktion (Subtraktion, wenn das Ergebnis nicht negativ ist) und Verschiebung implementiert werden.

Das ist natürlich nur ein grober Umriss.

Answer 2

Ein typischer Ansatz für eine 32/16: 16 + 16-Division wäre, die Dividende in einem Paar von 16-Bit-Registern (die während des Betriebs aktualisiert werden) und dem Divisor in einem eigenen Register zu speichern (was nicht funktioniert). t). Sechzehn Mal, subtrahiere die oberen 17 Bits des Dividenden vom Divisor; Wenn ein Borgen resultiert, verwerfe das Ergebnis und verschiebe den Divisor um eine Stelle nach links und setze eine 0 in die LSB. Wenn kein Borgen resultiert, speichern Sie das Ergebnis im Divisor, während Sie es nach links verschieben, aber setzen Sie eine 1 in den LSB. Nach sechzehn solchen Schritten halten die unteren 16 Bits des Dividendenregisters den Quotienten und die oberen 16 Bits den Rest. Beachten Sie, dass diese Operation nur funktioniert, wenn der Quotient in 16 Bits darstellbar ist. Man beachte auch, daß man bei einem Prozessor, der 32/16: 16 + 16-Teilung auf diese Weise implementiert, willkürlich große Zahlen durch eine 16-Bit-Menge teilen kann, da die oberen 16 Bit des Dividenden für jeden Schritt den Rest von sein sollten der vorherige Schritt.