Division algorithm

From Wikipedia, the free encyclopedia - View original article

 
  (Redirected from Division (digital))
Jump to: navigation, search

A division algorithm is an algorithm which, given two integers N and D, computes their quotient and/or remainder, the result of division. Some are applied by hand, while others are employed by digital circuit designs and software.

Division 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.

Discussion will refer to the form Q = N/D where

Contents

Division by subtraction

The proof that the quotient and remainder exist and are unique, described at Euclidean division, gives rise to a division algorithm using only additions, subtractions, and comparisons:

 function divide(N, D):   if D == 0 then throw DivisionByZeroException end   if D < 0 then (Q,R) = divide(N, -D); return (-Q, R) end   if N < 0 then (Q,R) = divide(-N, D); return (-Q - 1, D - R) end   // At this point, N ≥ 0 and D > 0   Q = 0; R = N   while  R' ≥ D do     Q = Q + 1     R = R - D   end   return (Q, R) end    

This procedure always produces R ≥ 0. Although very simple, it takes Ω(Q) steps, and so is exponentially slower than even slow division algorithms like long division. It is useful if Q is known to be small, and can serve as an executable specification.

Long division

Long division is the standard algorithm used for pen-and-paper division of multidigit numbers expressed in decimal notation. It shifts gradually from the left to the right end of the dividend, subtracting the largest possible multiple of the divisor at each stage; the multiples become the digits of the quotient, and the final difference is the remainder. When used with a binary radix, it forms the basis for the integer division (unsigned) with remainder algorithm below. Short division is an abbreviated form of long division suitable for one-digit divisors.

Integer division (unsigned) with remainder

The following algorithm, the binary version of the famous long division, will divide N by D, placing the quotient in Q and the remainder in R. All values are treated as unsigned integers.[citation needed]

 if D == 0 then throw DivisionByZeroException end Q := 0                    initialize quotient and remainder to zero R := 0                      for i = n-1...0 do   " where n is number of bits "   R := R << 1               left-shift R by 1 bit        R(0) := N(i)             set the least-significant bit of R equal to bit i of the numerator   if R >= D then     R = R - D                    Q(i) := 1   end end    

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:

Restoring division

Restoring division operates on fixed-point fractional numbers and depends on the following assumptions:[citation needed]

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  

The above restoring division algorithm can avoid the restoring step by saving the shifted value 2P before the subtraction in an additional register T (i.e., TP << 1) and copying register T to P when the result of the subtraction 2P − D is negative.

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.

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. Mask the positive term:P = 11101010\,
4. Sum P\, and \bar{N}:Q = 11010101\,

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 floating-point division bug was caused by an incorrectly coded lookup table. Five entries that were believed to be theoretically unreachable had been omitted from more than one thousand table entries.[1]

Fast division methods

Newton–Raphson division

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

The steps of Newton–Raphson are:

  1. Calculate an estimate for the reciprocal of the divisor (D): X_{0}.
  2. Compute successively more accurate estimates of the reciprocal: (X_{1},\ldots,X_{S})
  3. Compute the quotient by multiplying the dividend by the reciprocal of the divisor: Q = NX_{S}.

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)=DX-1, but the Newton–Raphson iteration for this is unhelpful since it cannot be computed without already knowing the reciprocal of D. Moreover multiple iterations for refining reciprocal are not possible since higher order derivatives do not exist for f(X). 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(1-DX_i) = X_i(2-DX_i)

which can be calculated from X_i using only multiplication and subtraction, or using two fused multiply–adds.

From a computation point of view the expressions X_{i+1} = X_i + X_i(1-DX_i) and X_{i+1} = X_i(2-DX_i) are not equivalent. To obtain a result with a precision of n bits while making use of the second expression one must compute the product between X_i and (2-DX_i) with double the required precision (2n bits). In contrast the product between X_i and (1-DX_i) need only be computed with a precision of n bits.

If the error is defined as \epsilon_i = D X_i - 1 \,, then

X_i = {1 \over D} (1 + \epsilon_i) \,
\epsilon_{i+1} = - {\epsilon_i}^2 \,.

Apply a bit-shift to the divisor D to scale it so that 0.5 ≤ D ≤ 1 . The same bit-shift should be applied to the numerator N so that the quotient does not change. Then one could use a linear approximation in the form

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

to initialize Newton–Raphson. To minimize the maximum of the absolute value of the error of this approximation on interval [0.5,1] one should use

X_0 = {48 \over 17} - {32 \over 17} D \,.[citation needed]

Using this approximation, the error of the initial value is less than

\vert \epsilon_0 \vert \leq {1 \over 17} \approx 0.059 \,.

Since for this method the convergence is exactly quadratic, it follows that

S = \left \lceil \log_2 \frac{P + 1}{\log_2 17} \right \rceil \,

steps is enough to calculate the value up to P \, binary places.

Goldschmidt division

Goldschmidt (after Robert Elliott Goldschmidt)[2] division uses an iterative process to repeatedly multiply both the dividend and divisor by a common factor Fi 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:

  1. Generate an estimate for the multiplication factor Fi .
  2. Multiply the dividend and divisor by Fi .
  3. If the divisor is sufficiently close to 1, return the dividend, otherwise, loop to step 1.

Assuming N/D has been scaled so that 0 < D < 1, each Fi is based on D:

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+1}}{F_{i+1}}.

After a sufficient number of iterations k: Q=N_k.

The Goldschmidt method is used in AMD Athlon CPUs and later models.[3][4]

Binomial theorem

The Goldschmidt method can be used with factors that allow simplifications by the binomial theorem. Assuming N/D has been scaled by a power of two such that D\in(\tfrac{1}{2},1]. We choose D = 1-x and F_{i} = 1+x^{2^i}. This yields

 \frac{N}{1-x}  = \frac{N\cdot(1+x)}{1-x^2}  = \frac{N\cdot(1+x)\cdot(1+x^2)}{1-x^4}  = \frac{N\cdot(1+x)\cdot(1+x^2)\cdot(1+x^4)}{1-x^8}.

Since x\in[0,\tfrac{1}{2}) after n steps we can round 1-x^{2^n} to 1 with a relative error of at most 2^{-n} and thus we obtain 2^n binary digits precision. This algorithm is referred to as the IBM method in.[5]

Large integer methods

Methods designed for hardware implementation generally do not scale to integers with thousands or millions of decimal digits; these frequently occur, for example, in modular reductions in cryptography. For these large integers, more efficient division algorithms transform the problem to use a small number of multiplications, which can then be done using an asymptotically efficient multiplication algorithm such as Toom–Cook multiplication or the Schönhage–Strassen algorithm. Examples include reduction to multiplication by Newton's method as described above[6] as well as the slightly faster Barrett reduction algorithm.[7] Newton's method's is particularly efficient in scenarios where one must divide by the same divisor many times, since after the initial Newton inversion only one (truncated) multiplication is needed for each division.

Division by a constant

Division by a constant is equivalent to multiplication by its reciprocal. Since the denominator D is constant, so is its reciprocal (1/D). Thus it is possible to compute the value of (1/D) once at compile time, and at run time perform the multiplication N·(1/D) rather than the division N/D. In floating point arithmetic the use of (1/D) presents no problem, but in integer the reciprocal will always evaluate to zero, assuming |D| > 1.

Note that it is not necessary to use specifically (1/D), as any value (X/Y) that reduces to the same is equivalent. For example, for division by 3 you could multiply by 1/3, 2/6, 3/9, or 194/582. This way, you can choose Y to be any power of two, and replace the division step with a fast right bit shift. The effect of calculating N/D as (N·X)/Y is replacing a division by a multiply and a shift. Note that the parentheses are important, as N·(X/Y) will evaluate to zero.

However, unless D itself is a power of two, there is no X and Y that satisfies the conditions above. But it is not necessary for (X/Y) to be exactly equal to 1/D, only that it is "close enough" and such that the error introduced by this approximation is in the bits that are discarded by the shift operation. For further details see the reference.[8]

As a concrete example, for 32 bit unsigned integers, division by 3 can be replaced with a multiply by 2863311531 / 2^{33}, a multiplication by 2863311531 followed by a 33 right bit shift. This value is equal to 1/2.999999999650754.

In some cases, division by a constant can be accomplished in even less time by converting the "multiply by a constant" into a series of shifts and adds or subtracts.[9] Of particular interest is division by 10, for which the exact quotient is obtained, with remainder if required.[10]

Rounding error

Round-off error can be introduced by division operations due to limited precision.

See also

References

  1. ^ Intel Corporation, 1994, Retrieved 2011-10-19,"Statistical Analysis of Floating Point Flaw"
  2. ^ Robert E. Goldschmidt, Applications of Division by Convergence, MSc dissertation, M.I.T., 1964
  3. ^ 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
  4. ^ 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
  5. ^ Paul Molitor, "Entwurf digitaler Systeme mit VHDL"
  6. ^ Hasselström, Karl (2003). Fast Division of Large Integers: A Comparison of Algorithms (Master's in Computer Science thesis). Royal Institute of Technology. http://www.treskal.com/kalle/exjobb/original-report.pdf. Retrieved 2011-03-23. 
  7. ^ Paul Barrett (1987). "Implementing the Rivest Shamir and Adleman public key encryption algorithm on a standard digital signal processor". Proceedings on Advances in cryptology---CRYPTO '86. London, UK: Springer-Verlag. pp. 311–323. ISBN 0-387-18047-8. http://portal.acm.org/citation.cfm?id=36688. 
  8. ^ Division by Invariant Integers using Multiplication Torbjörn Granlund and Peter L. Montgomery. ACM SIGPLAN Notices Vol 29 Issue 6 (June 1994) 61–72
  9. ^ Massmind: "Binary Division by a Constant"
  10. ^ R. A. Vowels, "Divide by 10", Australian Computer Journal (24), 1992, pp. 81-85.

External links