Goldschmidt division algorithm05. Dec '13

Introduction

Goldschmidt division is iterative division algorithm deployed in many processors. Higher precision can be achieved by adding fraction bits for intermediate calculations or by having more iterations.

Given

Dividend:

\begin{equation*} N_{-1} = 86_{10} = 01010110.000000000000_{2} \end{equation*}

Divisor:

\begin{equation*} D_{-1} = 7_{10} = 00000111.000000000000_{2} \end{equation*}

Correct result:

\begin{equation*} Q = \frac{N_{-1}}{D_{-1}} = 12.285714285714285714285714285714285714285714285714 \end{equation*}

Initial reciprocal is the inverse of divisor which is calculated by shifting bits around the fraction point:

\begin{equation*} F_{-1} = \frac{1}{D_{-1}} \approx 0.0546875_{10} = 00000000.000011100000_{2} \end{equation*}

In this case we have 8 bits for integers and 12 bits for fraction digits.

Algorithm steps

Iteration #1:

\begin{equation*} N_{0} = F_{-1} \times N_{-1} = 4.703125_{10} = 00000100.101101000000_{2} \end{equation*}
\begin{equation*} D_{0} = F_{-1} \times D_{-1} = 0.3828125_{10} = 00000000.011000100000_{2} \end{equation*}
\begin{equation*} F_{0} = 2 - D_{0} = 1.6171875_{10} = 00000001.100111100000_{2} \end{equation*}

Iteration #2:

\begin{equation*} N_{1} = F_{0} \times N_{0} = 7.605712890625_{10} = 00000111.100110110001_{2} \end{equation*}
\begin{equation*} D_{1} = F_{0} \times D_{0} = 0.618896484375_{10} = 00000000.100111100111_{2} \end{equation*}
\begin{equation*} F_{1} = 2 - D_{1} = 1.381103515625_{10} = 00000001.011000011001_{2} \end{equation*}

Iteration #3:

\begin{equation*} N_{2} = F_{1} \times N_{1} = 10.504150390625_{10} = 00001010.100000010001_{2} \end{equation*}
\begin{equation*} D_{2} = F_{1} \times D_{1} = 0.854736328125_{10} = 00000000.110110101101_{2} \end{equation*}
\begin{equation*} F_{2} = 2 - D_{2} = 1.145263671875_{10} = 00000001.001001010011_{2} \end{equation*}

Iteration #4:

\begin{equation*} N_{3} = F_{2} \times N_{2} = 12.02978515625_{10} = 00001100.000001111010_{2} \end{equation*}
\begin{equation*} D_{3} = F_{2} \times D_{2} = 0.978759765625_{10} = 00000000.111110101001_{2} \end{equation*}
\begin{equation*} F_{3} = 2 - D_{3} = 1.021240234375_{10} = 00000001.000001010111_{2} \end{equation*}

Iteration #5:

\begin{equation*} N_{4} = F_{3} \times N_{3} = 12.28515625_{10} = 00001100.010010010000_{2} \end{equation*}
\begin{equation*} D_{4} = F_{3} \times D_{3} = 0.99951171875_{10} = 00000000.111111111110_{2} \end{equation*}
\begin{equation*} F_{4} = 2 - D_{4} = 1.00048828125_{10} = 00000001.000000000010_{2} \end{equation*}

Conclusion

The result after 5 iterations is:

\begin{equation*} N_{5} = 12.28515625_{10} = 00001100.010010010000_{2} \end{equation*}

Which deviates from the correct result by:

\begin{equation*} 100\% - |\frac{N_5}{Q}| = 0.0045 \% \end{equation*}
TU Berlin Goldschmidt computer arithmetic division