Division (digital) Information & Division (digital) Links at HealthHaven.com

Several algorithms exist to perform division in digital designs. These algorithms fall into two main categories: slow division and fast division. Slow division algorithms produce one digit of the final quotient per iteration. Examples of slow division include restoring, non-performing restoring, non-restoring, and SRT division. Fast division methods start with a close approximation to the final quotient and produce twice as many digits of the final quotient on each iteration. Newton-Raphson and Goldschmidt fall into this category.

The following division methods are all based on the form $Q = N / D$ where

Q = Quotient
N = Numerator (dividend)
D = Denominator (divisor)

[edit] Slow division methods

Slow division methods are all based on a standard recurrence equation:

$P_{j+1} = R\times P_j - q_{n-(j+1)}\times D\,\!$

where:

P_j = the partial remainder of the division
R = the radix
q _{n-( j + 1)} = the digit of the quotient in position n-(j+1), where the digit positions are numbered from least-significant 0 to most significant n-1
n = number of digits in the quotient
D = the denominator

[edit] Restoring division

Restoring division operates on fixed-point fractional numbers and depends on the following assumptions:

N < D
0 < N,D < 1

The quotient digits q are formed from the digit set {0,1}.

The basic algorithm for binary (radix 2) restoring division is:

 P := N D := D << n              * P and D need twice the word width of N and Q for i = n-1..0 do        * for example 31..0 for 32 bits   P := 2P - D            * trial subtraction from shifted value   if P >= 0 then     q(i) := 1            * result-bit 1   else     q(i) := 0            * result-bit 0     P := P + D           * new partial remainder is (restored) shifted value   end end  where N=Numerator, D=Denominator, n=#bits, P=Partial remainder, q(i)=bit #i of quotient

Non-performing restoring division is similar to restoring division except that the value of 2*P[i] is saved, so D does not need to be added back in for the case of TP[i] ≤ 0.

[edit] Non-restoring division

Non-restoring division uses the digit set {−1,1} for the quotient digits instead of {0,1}. The basic algorithm for binary (radix 2) non-restoring division is:

 P[0] := N i := 0 while i < n do   if P[i] >= 0 then     q[n-(i+1)] := 1     P[i+1] := 2*P[i] - D   else     q[n-(i+1)] := -1     P[i+1] := 2*P[i] + D   end if   i := i + 1 end while

Following this algorithm, the quotient is in a non-standard form consisting of digits of −1 and +1. This form needs to be converted to binary to form the final quotient. Example:

Convert the following quotient to the digit set {0,1}:	$Q = 111\bar{1}1\bar{1}1\bar{1}$
Steps:
1. Mask the negative term:	$N = 00010101\,$
2. Form the two's complement of N:	$\bar{N} = 11101011$
3. Form the positive term:	$P = 11101010\,$
4. Sum $P\,$ and $\bar{N}$ :	$Q = 11010101\,$

[edit] SRT division

Named for its creators (Sweeney, Robertson, and Tocher), SRT division is a popular method for division in many microprocessor implementations. SRT division is similar to non-restoring division, but it uses a lookup table based on the dividend and the divisor to determine each quotient digit. The Intel Pentium processor's infamous divider bug was caused by an incorrectly coded lookup table. Five entries that were believed to be theoretically unreachable had been omitted from the more than one thousand table entries.

[edit] Fast division methods

[edit] Newton–Raphson division

Newton–Raphson uses Newton's method to converge to the quotient. The strategy of Newton–Raphson is to find the reciprocal of $D$ , and multiply that reciprocal by $N$ to find the final quotient $Q$ .

The steps of Newton–Raphson are:

Calculate an estimate for the reciprocal of the divisor ( $D$ ): $X 0$ . The estimate must be less than the final result.
Compute successively more accurate estimates of the reciprocal: $(X_{1},\ldots,X_{k})$
Compute the quotient by multiplying the dividend by the reciprocal of the divisor: $Q = N X k$

In order to apply Newton's method to find the reciprocal of $D$ , it is necessary to find a function $f (X)$ which has a zero at $X = 1 / D$ . The obvious such function is $f (X) = D X - 1$ , but the Newton–Raphson iteration for this is unhelpful since it cannot be computed without already knowing the reciprocal of $D$ . A function which does work is $f (X) = 1 / X - D$ , for which the Newton–Raphson iteration gives

$X_{i+1} = X_i - {f(X_i)\over f'(X_i)} = X_i - {1/X_i - D\over -1/X_i^2} = X_i + (X_i-DX_i^2) = X_i(2-DX_i)$

which can be calculated from $X i$ using only multiplication and subtraction.

Assuming the divisor is scaled (by a bit-shift operation) so that $0.5 < D < 1$ , the initial estimate for the reciprocal of the divisor can be calculated using the following linear approximation:

$\frac{1}{D} \approx X_0 = T_1 + T_2 D$

To minimize the maximum of the error of this approximation on interval $[0.5,1]$ one should use $T_1 = 3 / 2 + \sqrt{2}$ ≈ $2.9142$ and $T 2 = - 2$ , that is $X 0 = 2.9142 - 2 D$ . Using this approximation the error of the initial value is less than $3 / 2 - \sqrt{2}$ ≈ 0.0858, and thus since for Newton's method (for a zero of multiplicity 1) the convergence is at least quadratic, it follows that

$S = \left\lceil\log_2\frac{-N}{\log_2 0.0858}\right\rceil$

steps is enough to calculate the value up to $N$ binary places, for example, $S = 4$ steps is enough for $N = 32$ bits and $S = 5$ steps is enough for $N = 64$ bits.

[edit] Goldschmidt division

Goldschmidt (after Robert Elliott Goldschmidt)^[1] division uses series expansion to converge to the quotient. The strategy of Goldschmidt is to repeatedly multiply the dividend and divisor by a common factor F_i to converge the divisor, D, to 1 as the dividend, N, converges to the quotient Q:

$Q = \frac{N}{D} \frac{F_1}{F_1} \frac{F_2}{F_2} \frac{F_{\ldots}}{F_{\ldots}}$

The steps for Goldschmidt division are:

Generate an estimate for the multiply factor F_i.
Multiply the dividend and divisor by F_i.
Loop to step 1.

Assuming N/D has been scaled so $0 < D < 1$ , the first factor is:

F i + 1 = 2 - D i

Multiplying the dividend and divisor by the factor yields:

$\frac{N_{i+1}}{D_{i+1}} = \frac{N_{i}}{D_{i}}\frac{F_{i}}{F_{i}}$

After a sufficient number of iterations k: $Q = N k$

The Goldschmidt method is used in the divisor of the AMD Athlon CPUs and later models^[2],^[3].

[edit] Division by a constant

Division by a constant is equivalent to multiplication by its reciprocal. Integer division or modulo by a constant requires some adjustments round the multiply but the transformation is normally a very profitable optimization for a compiler.^[4]

Divisions by $2^n \pm 1$ gives an inverse with an easy repeating pattern such that a short sequence of shifts and adds or subtracts can be used instead of a multiply. This can be used if the multiply or loading the constant multiplier is slow.

[edit] Rounding error

Due to differences between how decimal and binary represent the same fraction, round-off error can be introduced by division operations due to limited precision.

Further information: Floating point

[edit] References

^ Robert E. Goldschmidt, Applications of Division by Convergence, MSc dissertation, M.I.T., 1964
^ 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
^ 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
^ Division by Invariant Integers using Multiplication Torbjörn Granlund and Peter L. Montgomery. ACM SIGPLAN Notices Vol 29 Issue 6 (June 1994) 61 - 72

[0] Robert E. Goldschmidt, Applications of Division by Convergence, MSc dissertation, M.I.T., 1964

[1] 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

[2] 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

[3] Division by Invariant Integers using Multiplication Torbjörn Granlund and Peter L. Montgomery. ACM SIGPLAN Notices Vol 29 Issue 6 (June 1994) 61 - 72

[1]

[2]

[3]

[4]

Contents