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 auch als die IBM-Methode bezeichnet.^[4]

Ä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, S. 106–115, 1999
3. 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
4. Michael Gregorius: Theorie des Logikentwurfs. (PDF; 687 kB) In: michaelgregorius.de. 16. September 2003, S. 87f., abgerufen am 15. November 2024.