# 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*}
Goldschmidt division computer arithmetic TU Berlin