imported>MarcoMA8: /* Binomische Formel */ Defekter Weblink ersetzt

2024-11-15T19:03:00Z

Binomische Formel: Defekter Weblink ersetzt

Neue Seite

Die '''Goldschmidt-Division''' ist ein Verfahren, um eine [[Division (Mathematik)|Division]] in einer [[Digitaltechnik|digitalen Schaltung]] schnell und mit geringem Hardwareaufwand zu realisieren.<ref>[https://dspace.mit.edu/bitstream/handle/1721.1/11113/34136725-MIT.pdf ''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 (Digitaltechnik)|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> [[Erweitern|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<sub>i</sub>''.
# Multipliziere Zähler und Nenner mit ''F<sub>i</sub>''.
# 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:

:<math>F_{i+1} = 2-N_i.</math>

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 [[Binomische Formel|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 [[Fehlerschranke|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>{{Internetquelle |autor=Michael Gregorius |url=https://michaelgregorius.de/zusammenfassungen/zusammenfassung-tdl-mg.pdf |titel=Theorie des Logikentwurfs |werk=michaelgregorius.de |datum=2003-09-16 |seiten=87f. |format=PDF; 687 kB |sprache=de |abruf=2024-11-15}}</ref>

== Ähnliche Verfahren ==
* [[SRT-Division]]
* [[Newton-Raphson-Division]]

== Einzelnachweise ==
<references />

[[Kategorie:Computerarithmetik]]

[[en:Goldschmidt division]]

Goldschmidt-Division - Versionsgeschichte

imported>MarcoMA8: /* Binomische Formel */ Defekter Weblink ersetzt