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 ${\displaystyle {\tfrac {Z}{N}}}$, welcher so lange mit dem Faktor ${\displaystyle F_{i}}$ 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.

${\displaystyle Q={\frac {Z}{N}}{\frac {F_{1}}{F_{1}}}{\frac {F_{2}}{F_{2}}}{\frac {F_{\ldots }}{F_{\ldots }}}.}$

Die auszuführenden Schritte sind:

1. Wähle einen geeigneten Faktor F_i.
2. Multipliziere Zähler und Nenner mit F_i.
3. Wenn der Nenner nahe genug an 1 herangekommen ist, gib den Zähler zurück, andernfalls fahre mit Schritt 1 fort.

Sind ${\displaystyle Z}$ und ${\displaystyle N}$ so skaliert, dass ${\displaystyle 0<N<1}$, dann können die Erweiterungsfaktoren ${\displaystyle F_{i}}$ einfach berechnet werden:

${\displaystyle F_{i+1}=2-N_{i}.}$

Damit ergibt sich:

${\displaystyle {\frac {Z_{0}}{N_{0}}}={\frac {Z}{N}},{\frac {Z_{i+1}}{N_{i+1}}}={\frac {Z_{i}F_{i+1}}{N_{i}F_{i+1}}}.}$

Nach einer genügend großen Zahl von Iterationen ${\displaystyle k}$ ist der gesuchte Quotient ${\displaystyle Q=Z_{k}}$.

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

Die Faktoren der Goldschmidt-Division können so gewählt werden, dass eine Vereinfachung mit der binomischen Formel möglich ist.

Angenommen ${\displaystyle {\tfrac {Z}{N}}}$ wurde mit einer Zweierpotenz so skaliert, dass ${\displaystyle N\in ({\tfrac {1}{2}},1]}$.

Wir setzen ${\displaystyle N=1-x}$ und ${\displaystyle F_{i+1}=1+x^{(2^{i})}}$.

Dann gilt:

${\displaystyle {\begin{aligned}{\frac {Z}{1-x}}&={\frac {Z\cdot (1+x)}{1-x^{2}}}\\&={\frac {Z\cdot (1+x)\cdot (1+x^{2})}{1-x^{4}}}\\&\vdots \\&={\frac {Z\cdot (1+x)\cdot (1+x^{2})\dotsm (1+x^{(2^{n-1})})}{1-x^{(2^{n})}}}\end{aligned}}}$

Da ${\displaystyle x\in [0,{\tfrac {1}{2}})}$ können wir nach ${\displaystyle n}$ Schritten ${\displaystyle 1-x^{(2^{n})}}$ zu 1 runden. Der maximale relative Fehler ist dabei ${\displaystyle 2^{-(2^{n})}}$, und wir erhalten eine Genauigkeit von ${\displaystyle 2^{n}}$ Digitalstellen. Dieser Algorithmus wird in^[4] als die IBM-Methode bezeichnet.

Ähnliche Verfahren

• SRT-Division
• Newton-Raphson-Division

Einzelnachweise

1. ↑ Applications of Division by Convergence by Robert E. Goldschmidt. Massachusetts Institute of Technology, 1964.
2. ↑ Stuart F. Oberman, "Floating Point Division and Square Root Algorithms and Implementation in the AMD-K7 Microprocessor", in Proc. IEEE Symposium on Computer Arithmetic, pp. 106–115, 1999
3. ↑ Peter Soderquist and Miriam Leeser, "Division and Square Root: Choosing the Right Implementation", IEEE Micro, Vol.17 No.4, pp.56–66, July/August 1997
4. ↑ Paul Molitor, „Entwurf digitaler Systeme mit VHDL“ (Memento des Originals vom 5. März 2012 im Internet Archive)  Info: Der Archivlink wurde automatisch eingesetzt und noch nicht geprüft. Bitte prüfe Original- und Archivlink gemäß Anleitung und entferne dann diesen Hinweis.@1@2Vorlage:Webachiv/IABot/mephisto.informatik.uni-halle.de