2

I have found in Gonzalez/Diaz-Herrera/Tucker: Computing Handbook an example for the Goldschmidt division in the case of real numbers. The example is the following: \begin{align} N_0 &= N = 0.625 \\ D_0 &= D = 0.75 \\ F_1 &= 1.3& & &\text{Table Look Up} \\ N_1 &= N_0 \cdot F_1 = 0.625 \cdot 1.3 &= 0.8125& &\text{Multiply} \\ D_1 &= D_0 \cdot F_1 = 0.75 \cdot 1.3 &= 0.975& &\text{Multiply} \\ F_2 &= 2 - D_1 = 2 - 0.975 &= 1.025& &\text{Subtract} \\ N_2 &= N_1 \cdot F_2 = 0.8125 \cdot 1.025 &= 0.8328125& &\text{Multiply} \\ D_2 &= D_1 \cdot F_2 = 0.975 \cdot 1.025 &= 0.999375& &\text{Multiply} \\ F_3 &= 2 - D_2 = 2 - 0.999375 &= 1.000625& &\text{Subtract} \\ N_3 &= N_2 \cdot F_3 = 0.8328125 \cdot 1.000625 &= 0.8333330078125& &\text{Multiply} \\ (D_3 &= D_2 \cdot F_3 = 0.999375 \cdot 1.000625 &= 0.999999609375)& &\text{(Multiply)} \\ \end{align} enter image description here

Even though the example is quite simple, I have problems in two parts:

  • How to get the estimate of 1.3 as the value of F1, it mentions one table, but how to use it?
  • In the case of division with integers, the procedure is the same? I have been trying to check it up one example for this case, but I only found explanations that use binaries and real numbers. If somebody could post an example of how to do this procedure with integer numbers would be great.

Thanks

greybeard
  • 103
Lila
  • 479
  • (In chapter 20 by Swartzlander, E. E., featuring in the introduction of his own Computer Arithmetic: Volume II, too.) – greybeard Feb 28 '21 at 16:36

1 Answers1

0

Let's try and divide 6250 by 75.
First, almost arbitrarily re-interpret as fixed point numbers 62.50 and 00.75.
Look up the reciprocal of leading digit .7: 1.4 $= F_1$
Products: $N_1 = 62.5 \cdot 1.4 = 87.5$, $D_1 = .75 \cdot 1.4 = 1.05$
$F_2 = 2-1.05 = .95$, $N_2 = 87.5\cdot.95 = 83.12(5)$
($D_2 = 1.05\cdot.95 = .99(75)$, but talking integers, 83 is the quotient)

With integers, one may pre-check the absolute value of the dividend for being smaller than the divisor. To profit most from the table of reciprocals, the operands conventionally are scaled such that the divisor is in a smallish range, its most significant digit in a known position.
Choosing the size of the reciprocal table is a trade-off between small table and small number of iterations.
The most significant part/first few digits of the divisor are used to index the table, yielding a reciprocal with a similar number of digits of resolution.
Thinking of the bit patterns as fixed point numbers with more significant half integers, less significant part fractions is just a convenience - otherwise, I'd have to hand-wave about scaling all the time.

greybeard
  • 103
  • (The approximation 1.3 from the example is due to using two digits (.75) in stead of the single one used in above answer.) – greybeard Feb 28 '21 at 17:46