Division (digital)

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, nonperforming restoring, nonrestoring, 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. NewtonRaphson 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).
Contents
Slow division methods
Slow division methods are all based on a standard recurrence equation:
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 leastsignificant 0 to most significant n1
 n = number of digits in the quotient
 D = the denominator.
Restoring division
Restoring division operates on fixedpoint fractional numbers and depends on the following assumptions:
 D < N
 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 = n1..0 do * for example 31..0 for 32 bits P := 2P  D * trial subtraction from shifted value if P >= 0 then q(i) := 1 * resultbit 1 else q(i) := 0 * resultbit 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., T=P<<1) and copying register T to P when the result of the subtraction 2P  D is negative.
Nonperforming 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 ofTP[i] ≤ 0
.Nonrestoring division
Nonrestoring division uses the digit set {−1,1} for the quotient digits instead of {0,1}. The basic algorithm for binary (radix 2) nonrestoring 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 nonstandard 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}: Steps: 1. Mask the negative term: 2. Form the two's complement of N: 3. Form the positive term: 4. Sum and : 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 nonrestoring 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 floatingpoint 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:
 Calculate an estimate for the reciprocal of the divisor (D): X_{0}.
 Compute successively more accurate estimates of the reciprocal:
 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. A function which does work is f(X) = 1 / X − D, for which the Newton–Raphson iteration gives
which can be calculated from X_{i} using only multiplication and subtraction, or using two fused multiply–adds.
If the error is defined as then
Apply a bitshift to the divisor D to scale it so that 0.5 ≤ D ≤ 1 . The same bitshift should be applied to the numerator N so that the quotient does not change. Then one could use a linear approximation in the form
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
Using this approximation, the error of the initial value is less than
Since for this method the convergence is exactly quadratic, it follows that
steps is enough to calculate the value up to 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 F_{i} to converge the divisor, D, to 1 as the dividend, N, converges to the quotient Q:
The steps for Goldschmidt division are:
 Generate an estimate for the multiplication factor F_{i} .
 Multiply the dividend and divisor by F_{i} .
 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 F_{i} is based on D:
 F_{i + 1} = 2 − D_{i}.
Multiplying the dividend and divisor by the factor yields:
 .
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 . We choose D = 1 − x and . This yields . Since after n steps we can round 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 rather than the division (N / D)
When doing floating point arithmetic the use of (1 / D) presents no problem. But when doing integer arithmetic it is problematic, as (1 / D) will always evaluate to zero (assuming D > 1), so it is necessary to do some manipulations to make it work.
Note that it is not necessary to use (1 / D). Any value (X / Y) will work as long as it reduces to (1 / D). For example, for division by 3 the reciprocal is 1/3. So the division could be changed to multiplying by 1/3, but it could also be a multiplication by 2/6, or 3/9, or 194/582. So the desired operation of (N / D) can be changed to , where (X / Y) equals (1 / D). Although the quotient (X / Y) would still evaluate to zero, it is possible to do another adjustment and reorder the operations to produce .
This form appears to be less efficient because it involves both a multiplication and a division, but if Y is a power of two, then the division can be replaced by a fast bit shift. So the effect is to replace a division by a multiply and a shift.
There's one final obstacle to overcome  in general it is not possible to find values X and Y such that Y is a power of 2 and (X / Y) = (1 / D). But it turns out that it is not necessary for (X / Y) to be exactly equal to (1 / D) in order to get the correct final result. It is sufficient to find values for X and Y such that (X / Y) is "close enough" to (1 / D). Note that the shift operation loses information by throwing away bits. It is always possible to find values of X and Y (with Y being a power of 2) such that the error introduced by the fact that (X / Y) is only approximately equal to (1 / D) is in the bits that are discarded. For further details please see the reference.^{[8]}As a concrete example  for 32 bit unsigned integers, division by 3 can be replaced with a multiply by . The denominator in this case is equal to 2^{33}.
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]}Rounding error
Roundoff error can be introduced by division operations due to limited precision.
Further information: Floating pointSee also
References
 ^ Intel Corporation, 1994, Retrieved 20111019,"Statistical Analysis of Floating Point Flaw"
 ^ 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 AMDK7 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
 ^ Paul Molitor, "Entwurf digitaler Systeme mit VHDL"
 ^ 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/originalreport.pdf. Retrieved 20110323.
 ^ Paul Barrett (1987). "Implementing the Rivest Shamir and Adleman public key encryption algorithm on a standard digital signal processor". Proceedings on Advances in cryptologyCRYPTO '86. London, UK: SpringerVerlag. pp. 311–323. ISBN 0387180478. http://portal.acm.org/citation.cfm?id=36688.
 ^ Division by Invariant Integers using Multiplication Torbjörn Granlund and Peter L. Montgomery. ACM SIGPLAN Notices Vol 29 Issue 6 (June 1994) 61  72
 ^ Massmind: "Binary Division by a Constant"
External links
 Computer Arithmetic Algorithms JavaScript Simulator  contains simulators for many different division algorithms
Categories: Computer arithmetic
Wikimedia Foundation. 2010.
Look at other dictionaries:
Division — may refer to: Contents 1 Mathematics 2 Science 3 Society 4 … Wikipedia
Division (mathematics) — Divided redirects here. For other uses, see Divided (disambiguation). For the digital implementation of mathematical division, see Division (digital). In mathematics, especially in elementary arithmetic, division (÷ … Wikipedia
Digital — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Sur les autres projets Wikimedia : « Digital », sur le Wiktionnaire (dictionnaire universel) Le terme digital est : l adjectif associé … Wikipédia en Français
Division algorithm — This article is about a mathematical theorem. For a list of division algorithms, see Division (digital). In mathematics, and more particularly in arithmetic, the usual process of division of integers producing a quotient and a remainder can be… … Wikipedia
Digital Domain — Productions Type Privately held company Industry Visual effects, CGI animation Found … Wikipedia
Digital+ — Saltar a navegación, búsqueda Digital+ es una plataforma de pago de televisión por satélite, que opera en España a través de los satélites Astra e Hispasat. Es propiedad de Sogecable, participada mayoritariamente por el Grupo PRISA. Inició sus… … Wikipedia Español
Digital Signal 1 — (DS1, sometimes DS 1) is a T carrier signaling scheme devised by Bell Labs.[1] DS1 is a widely used standard in telecommunications in North America and Japan to transmit voice and data between devices. E1 is used in place of T1 outside North… … Wikipedia
Digital (Joy Division song) — Digital Song by Joy Division from the album A Factory Sample Released December 1978 Recorded Cargo Studios Rochdale, Lancs, 11 October 1978 Genre Post punk … Wikipedia
Digital Domain Park — Former names Thomas J. White Stadium (1988–2004) Tradition Field (2005–2010) … Wikipedia
Digital geologic mapping — is the process by which geologic features are observed, analyzed, and recorded in the field and displayed in real time on a computer or personal digital assistant (PDA). The primary function of this emerging technology is to produce spatially… … Wikipedia