Goldschmidt-Division
Die Goldschmidt-Division ist ein Verfahren, um eine Division in einer digitalen Schaltung schnell und mit geringem Hardwareaufwand zu realisieren.[1] Dabei wird die Division auf eine Multiplikation zurückgeführt, womit bereits evtl. vorhandene Multiplizierer mitverwendet werden können.
Der Ansatz der Goldschmidt-Division ist die Betrachtung der Division als Bruch , welcher so lange mit dem Faktor erweitert wird, bis der Nenner nahe genug an den Wert 1 konvergiert ist. Der Wert des Zählers entspricht somit dann dem Ergebnis der Division.
Die auszuführenden Schritte sind:
- Wähle einen geeigneten Faktor Fi.
- Multipliziere Zähler und Nenner mit Fi.
- Wenn der Nenner nahe genug an 1 herangekommen ist, gib den Zähler zurück, andernfalls fahre mit Schritt 1 fort.
Sind und so skaliert, dass , dann können die Erweiterungsfaktoren einfach berechnet werden:
Damit ergibt sich:
Nach einer genügend großen Zahl von Iterationen ist der gesuchte Quotient .
Bei der Umsetzung als Schaltung können die Multiplikationen von Nenner und Zähler parallel durchgeführt werden, was eine schnelle Abarbeitung des Algorithmus ermöglicht. Die Goldschmidt-Division wird in den AMD-Athlon-CPUs und späteren Modellen verwendet.[2][3]
Binomische Formel
BearbeitenDie Faktoren der Goldschmidt-Division können so gewählt werden, dass eine Vereinfachung mit der binomischen Formel möglich ist.
Angenommen wurde mit einer Zweierpotenz so skaliert, dass .
Wir setzen und .
Dann gilt:
Da können wir nach Schritten zu 1 runden. Der maximale relative Fehler ist dabei , und wir erhalten eine Genauigkeit von Digitalstellen. Dieser Algorithmus wird auch als die IBM-Methode bezeichnet.[4]
Ähnliche Verfahren
BearbeitenEinzelnachweise
Bearbeiten- ↑ Applications of Division by Convergence by Robert E. Goldschmidt. Massachusetts Institute of Technology, 1964.
- ↑ Stuart F. Oberman, "Floating Point Division and Square Root Algorithms and Implementation in the AMD-K7 Microprocessor", in Proc. IEEE Symposium on Computer Arithmetic, S. 106–115, 1999
- ↑ Peter Soderquist and Miriam Leeser, "Division and Square Root: Choosing the Right Implementation", IEEE Micro, Band 17 No.4, S. 56–66, July/August 1997
- ↑ Michael Gregorius: Theorie des Logikentwurfs. (PDF; 687 kB) In: michaelgregorius.de. 16. September 2003, S. 87f., abgerufen am 15. November 2024.