g-rh@cca.UUCP (Richard Harter) (06/13/84)
{
A recent submission asked for a good algorithm for division,
given shift, multiply, and add instructions. The following is an
efficient and simple algorithm:
Suppose we have an approximation x to 1/N. Then we have
xN = 1+e which can be written as 1/N = x/(1+e). We have
1/(1+e) = 1-e+e^2-e^3+e-4 ...
= (1-e)(1+e^2)(1+e^4)(1+e^8)...
An estimate for x which is correct to the first bit can be found
by shifting N. This should be done so that xN lies in the range
[1/2,1]. The magnitude of the error term, e, is then bounded by
1/2. Four terms in the product are required for 16 bit accuracy
and five for 32 bit accuracy. The powers are formed by successive
squaring. A number of refinements are possible; the best algorithm
for a particular machine will depend on the exact instruction set
available and their execution times.
}