Goldschmidt-Division

Die Goldschmidt-Division ist ein Verfahren, um eine Division in einer digitalen Schaltung schnell und mit geringem Hardwareaufwand zu realisieren.<ref>Applications of Division by Convergence by Robert E. Goldschmidt. Massachusetts Institute of Technology, 1964.</ref> 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 <math>\tfrac{Z}{N}</math>, welcher so lange mit dem Faktor <math>F_i</math> 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.

<math>Q = \frac{Z}{N} \frac{F_1}{F_1} \frac{F_2}{F_2} \frac{F_{\ldots}}{F_{\ldots}}.</math>

Die auszuführenden Schritte sind:

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

Sind <math>Z</math> und <math>N</math> so skaliert, dass <math>0 < N < 1</math>, dann können die Erweiterungsfaktoren <math>F_i</math> einfach berechnet werden:

Damit ergibt sich:

<math>

\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}}. </math>

Nach einer genügend großen Zahl von Iterationen <math>k</math> ist der gesuchte Quotient <math>Q=Z_k</math>.

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.<ref>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</ref><ref>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</ref>

Binomische Formel

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

Angenommen <math>\tfrac{Z}{N}</math> wurde mit einer Zweierpotenz so skaliert, dass <math>N\in(\tfrac{1}{2},1]</math>.

Wir setzen <math>N = 1-x</math> und <math>F_{i+1} = 1+x^{(2^i)}</math>.

Dann gilt:

<math>

\begin{align} \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{align} </math>

Da <math>x\in[0,\tfrac{1}{2})</math> können wir nach <math>n</math> Schritten <math>1-x^{(2^n)}</math> zu 1 runden. Der maximale relative Fehler ist dabei <math>2^{-(2^n)}</math>, und wir erhalten eine Genauigkeit von <math>2^n</math> Digitalstellen. Dieser Algorithmus wird auch als die IBM-Methode bezeichnet.<ref>Michael Gregorius: Theorie des Logikentwurfs. (PDF; 687 kB) In: michaelgregorius.de. 16. September 2003, S. 87f., abgerufen am 15. November 2024. </ref>

Einzelnachweise

Binomische Formel

Ähnliche Verfahren

Einzelnachweise