Goldschmidt-Division

Die Goldschmidt-Division ist ein Verfahren, um eine Division in einer digitalen Schaltung schnell und mit geringem Hardwareaufwand zu realisieren. 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 $\frac{Z}{N}$, welcher so lange mit dem Faktor $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.

$Q=\frac{Z}{N}\frac{F_1}{F_1}\frac{F_2}{F_2}\frac{F_{\dots }}{F_{\dots }}.$

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 $Z$ und $N$ so skaliert, dass $0<N<1$, dann können die Erweiterungsfaktoren $F_i$ einfach berechnet werden:

$F_{i+1}=2-N_i.$

Damit ergibt sich:

$\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 $k$ ist der gesuchte Quotient $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.

Binomische Formel

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

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

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

Dann gilt:

$\begin{array}{cc}\frac{Z}{1-x}& =\frac{Z\cdot (1+x)}{1-x^2}\\ & =\frac{Z\cdot (1+x)\cdot (1+x^2)}{1-x^4}\\ & ⋮\\ & =\frac{Z\cdot (1+x)\cdot (1+x^2)\cdots (1+x^{(2^{n-1})})}{1-x^{(2^n)}}\end{array}$

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

Ähnliche Verfahren

• SRT-Division
• Newton-Raphson-Division