Goldschmidt Division

The Goldschmidt Division is a method for realizing a division in a digital circuit quickly and with little hardware expenditure. The division is reduced to a multiplication, which means that multipliers that may already be present can also be used.

The Goldschmidt division approach is to consider the division as a fraction , which is expanded by the factor until the denominator has converged close enough to the value 1. The value of the counter then corresponds to the result of the division. ${\displaystyle {\tfrac {Z}{N}}}$ ${\displaystyle F_{i}}$

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

The steps to follow are:

1. Choose an appropriate factor F _i .
2. Multiply the numerator and denominator by F _i .
3. If the denominator is close enough to 1, return the numerator, otherwise go to step 1.

If and are scaled in such a way that the expansion factors can easily be calculated: ${\displaystyle Z}$ ${\displaystyle N}$ ${\displaystyle 0<N<1}$ ${\displaystyle F_{i}}$

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

This results in:

${\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}}}.}$

After a sufficiently large number of iterations , the quotient we are looking for is . ${\displaystyle k}$ ${\displaystyle Q=Z_{k}}$

When implemented as a circuit, the multiplications of denominator and numerator can be carried out in parallel, which enables the algorithm to be processed quickly. The Goldschmidt division is used in the AMD - Athlon -CPUs and later models.

Binomial formula

The factors of the Goldschmidt division can be chosen in such a way that a simplification with the binomial formula is possible.

It was assumed that a power of two was scaled so that . ${\displaystyle {\tfrac {Z}{N}}}$ ${\displaystyle N\in ({\tfrac {1}{2}},1]}$

We put and . ${\displaystyle N=1-x}$ ${\displaystyle F_{i+1}=1+x^{(2^{i})}}$

Then:

${\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}}}$

Since we can to step round to-1. The maximum relative error is included and we get an accuracy of digital digits. This algorithm is referred to as the IBM method. ${\displaystyle x\in [0,{\tfrac {1}{2}})}$ ${\displaystyle n}$ ${\displaystyle 1-x^{(2^{n})}}$ ${\displaystyle 2^{-(2^{n})}}$ ${\displaystyle 2^{n}}$

Similar procedures

• SRT division
• Newton-Raphson Division

Individual evidence

1. ^ Applications of Division by Convergence by Robert E. Goldschmidt.  ( Page no longer available , search in web archives )  Info: The link was automatically marked as defective. Please check the link according to the instructions and then remove this notice. 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, "Draft digital systems with VHDL" ( Memento of the original from March 5, 2012 in the Internet Archive ) Info: The archive link was automatically inserted and not yet checked. Please check the original and archive link according to the instructions and then remove this notice.