Wie kommt es in unseren Computern zur Teilung?

17

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.

Programm-o-Steve
quelle
1
@ program-o-steve Division in einer ALU ist eine komplexe Operation. Sie erhalten kein "einfaches" Flussdiagramm.
Majenko
5
@ Leon Heller Oh! Das sagt es nicht. Dies ist eine reine Hardware-Frage
program-o-steve
2
@ Leon Heller Ich denke, es ist nicht ...., die Elektronik, physikalische Computer gehören ...
Programm-o-Steve
2
Die Aufteilung in Mikrocontroller ist nicht einfach. Es gibt schnelle und langsame Wege, dies zu tun. Langsame Wege sind leichter zu verstehen, aber die schnellen Wege werden in modernen CPUs verwendet. Worüber möchten Sie speziell informiert werden? Möchten Sie nur ein grundlegendes Verständnis der Prinzipien oder eine detaillierte Analyse moderner CPUs?
Konsalik
4
@LeonHeller Normalerweise stimme ich den Fragen zu, die geschlossen werden sollen, aber das CPU-Design ist in hohem Maße eine elektrotechnische Frage. Diese Frage könnte etwas Hilfe gebrauchen, um klarer zu machen, was gewünscht wird (wie etwa was konsalik fragt), aber das macht es nicht zum Thema.
Kellenjb

Antworten:

17

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:

  1. 73=4
  2. 43=1
  3. 1<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:

Bildbeschreibung hier eingeben

Wobei jeder 1-Bit-Volladdierer wie folgt implementiert wird:

Bildbeschreibung hier eingeben

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:

Q.=ND

Diese Methode funktioniert wie folgt:

  1. N und D mit einem Bruch F so multiplizieren, dass D gegen 1 geht.
  2. Wenn sich D 1 nähert, nähert sich N Q

Diese Methode verwendet die binäre Multiplikation durch iterative Addition, die auch in modernen AMD-CPUs verwendet wird.

Konsalik
quelle
1
Einige Flussdiagramme für Variationen der "langsamen" Methode (implementiert in der Montage auf Mikros ohne Hardwareteilung, aber dennoch hilfreich) sind in der AVR200- Appnote von Atmel enthalten.
Kevin Vermeer
Können Sie bitte eine Illustration zur Goldschmidt-Teilungsmethode geben ? Auch das hier angegebene Flussdiagramm ist ein Beispiel für langsame Teilung.
Programm-o-Steve
nach welcher methode müssen wir die dividende immer wieder nach links verschieben?
Programm-o-Steve
@ program-o-steve Hier ist eine kurze Illustration: finde 22/7 (pi approximation). Multiplizieren Sie zuerst oben und unten mit 0,1, um 2,2 / 0,7 zu ​​erhalten. Multiplizieren Sie erneut mit 1,3 und geben Sie 2,86 / 0,91. Verwenden Sie 1,09 und geben Sie 3,1174 / 0,9919. 1.000000 ...
Alan Campbell
Wie kann man "mit einem Bruchteil multiplizieren"? Brüche sind im Gleitkomma nicht darstellbar. Ein Bruch ist per Definition ein Zähler geteilt durch den Nenner, so dass Sie in einem zirkulären Argument bleiben, dass Sie immer noch teilen müssen. Und wie schätzt man diesen Bruch überhaupt?
CogitoErgoCogitoSum
4

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)

  1. Zerlegen der Gleitkommazahlen in Vorzeichen (+1 oder -1), Mantisse ("a" und "b") und Exponenten (binäre Ganzzahl)
  2. das Vorzeichen des Ergebnisses ist (+1), wenn beide Vorzeichen gleich sind, sonst (-1)
  3. Exponenten werden subtrahiert (Exponent von B von Exponent von A subtrahiert), um den Exponenten des Ergebnisses zu bilden
  4. 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).

  5. einb=einrecichprÖceinl(b)brecichprÖceinl(b)

  6. d==1+ϵ
    d(2-d)=(1+ϵ)×(1-ϵ)=1-ϵ2
  7. Der Zähler, nun da der Nenner genau '1' ist, ist die Mantisse des Ergebnisses und kann mit dem zuvor berechneten Vorzeichen und Exponenten kombiniert werden.
  8. IEEE-Gleitkomma erlaubt einige Ausnahmen (denormalisierte Zahlen, NAN; diese müssen von anderen logischen Operationen behandelt werden.

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).

Whit3rd
quelle
1

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.

richard1941
quelle
-1

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

user59608
quelle
Willkommen bei EE.SE. Von Nur-Link-Antworten wird abgeraten. Bitte fassen Sie die Informationen im Link zusammen.
Null
Tun sie. Tonnen von CPUs haben immer noch keine Single Cycle Multiplikatoren und verwenden Software-Multiplikation.
user3528438