Wie kommt es zu einer Teilung in digitalen Computern? Was ist der Algorithmus dafür?
Ich habe intensiv in Google gesucht, aber keine zufriedenstellenden Ergebnisse erzielt. Bitte geben Sie einen sehr übersichtlichen Algorithmus / Ablaufplan für den Teilungsalgorithmus mit einer Beispielillustration an.
computers
tutorial
arithmetic-division
Programm-o-Steve
quelle
quelle
Antworten:
Unterteilungsalgorithmen in digitalen Entwürfen können in zwei Hauptkategorien unterteilt werden. Langsame und schnelle Teilung.
Ich schlage vor, Sie lesen nach, wie die binäre Addition und Subtraktion funktioniert, wenn Sie mit diesen Konzepten noch nicht vertraut sind.
Langsame Division
Die einfachsten langsamen Methoden funktionieren alle folgendermaßen: Subtrahieren Sie den Nenner vom Zähler. Tun Sie dies rekursiv mit dem Ergebnis jeder Subtraktion, bis der Rest kleiner als der Nenner ist. Die Anzahl der Iterationen ist der ganzzahlige Quotient, und die verbleibende Anzahl ist der Rest.
Beispiel:
7/3:
Die Antwort ist also 2 mit einem Rest von 1. Um diese Antwort ein bisschen relevanter zu machen, hier einige Hintergrundinformationen. Eine binäre Subtraktion durch Addition des Negativs wird durchgeführt, z. B .: 7 - 3 = 7 + (-3). Dies wird durch Verwendung des Zweierkomplements erreicht. Jede Binärzahl wird mit einer Reihe von Volladdierern addiert:
Wobei jeder 1-Bit-Volladdierer wie folgt implementiert wird:
Schnelle Division
Die langsamere Aufteilungsmethode ist zwar leicht zu verstehen, erfordert jedoch wiederholte Iterationen. Es gibt verschiedene "schnelle" Algorithmen, die jedoch alle auf Schätzungen beruhen.
Betrachten Sie die Goldschmidt-Methode:
Diese Methode funktioniert wie folgt:
Diese Methode verwendet die binäre Multiplikation durch iterative Addition, die auch in modernen AMD-CPUs verwendet wird.
quelle
Hardware für die Gleitkommadivision ist Teil einer Logikeinheit, die auch die Multiplikation durchführt. Es ist ein Multiplikator-Hardwaremodul verfügbar. Gleitkommazahlen wie A und B werden durch geteilt (A / B)
Mantissen (die Binärziffern der Zahlen) sind Festkommazahlen zwischen 1/2 und 1; Das bedeutet, dass die erste Ziffer nach dem Binärpunkt '1' ist, gefolgt von Nullen und Einsen. Als ersten Schritt findet eine Nachschlagetabelle den Kehrwert mit einer Genauigkeit von sechs Bits (es gibt nur 32 Möglichkeiten, es ist eine kleine Tabelle).
Interessanterweise wurde der alte Pentium-Divide-Bug (1994 sehr neu) durch einen Druckfehler verursacht, der fehlerhafte Kehrwerttabellenwerte für Schritt (4) verursachte. Eine frühe Veröffentlichung, "Eine Teilungsmethode unter Verwendung eines Parallelmultiplikators", Domenico Ferrari, IEEE Trans. Elektron. Comput. EC-16 / 224-228 (1967) beschreibt das Verfahren ebenso wie "The IBM System / 360 Model 91: Gleitkomma-Ausführungseinheit" IBM J. Res. No. Dev. 11 : 34 & ndash; 53 (1967).
quelle
Abhängig von den zu behandelnden Nummern gibt es sehr unterschiedliche Aufteilungsmethoden. Für ganze Zahlen funktioniert die von anderen angegebene Shift-and-Subtract-Methode einwandfrei. Bei Gleitkommazahlen kann es jedoch schneller sein, zuerst den Kehrwert des Nenners zu berechnen und dann diesen Wert mit Ihrem Zähler zu multiplizieren.
Die Berechnung des Kehrwerts des Nenners ist nicht so schlecht; Dies geschieht durch Verfeinerung aufeinanderfolgender Approximationen. Lassen Sie g Ihre Vermutung für 1 / d sein. Verwenden Sie für eine bessere Vermutung g '= g (2-gd). Dies konvergiert quadratisch, sodass Sie bei jeder Verbesserung die doppelte Genauigkeit erzielen.
Beispiel: Berechnen Sie den Kehrwert von 3.5.
Ihre anfängliche Schätzung ist 0.3. Sie berechnen 0,3 * 3,5 = 1,15. Ihre angepasste Schätzung ist 0,3 * (2 - 1,15) = 0,285. Schon ziemlich nah! Wiederholen Sie den Vorgang, und Sie erhalten 0,2857125, und ein dritter Versuch erhält 0,2857142857.
Es gibt einige Abkürzungen. Im Gleitkomma-Modus können Sie Potenzen von zehn oder Zweierpotenzen extrahieren, abhängig von der Zahlenbasis Ihres Computers. Und um die Geschwindigkeit auf Kosten eines höheren Speicherverbrauchs zu erhöhen, können Sie eine vorberechnete Tabelle für Zahlen im Bereich von 1 bis b (wobei b Ihre Zahlenbasis ist) verwenden, um eine Vermutung zu erhalten, die dem erforderlichen Kehrwert und unmittelbar nahe kommt Speichern Sie einen oder zwei Verfeinerungsschritte.
Denken Sie daran, dass Sie, wie bei der Vervielfältigung und der Verlegenheit Kolmogorovs 1960 durch seinen Studenten Anatoly Karatsuba, nie wissen, wann eine schnellere oder bessere Methode gefunden wird. Gib niemals deine Neugierde auf.
quelle
Computer machen keine iterative Addition zur Multiplikation von Zahlen - es wäre wirklich langsam. Stattdessen gibt es einige schnelle Multiplikationsalgorithmen. Check out: http://en.wikipedia.org/wiki/Karatsuba_algorithm
quelle