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 1 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. In mathematics, especially in elementary arithmetic, division is an arithmetic operation which is the inverse of multiplication, and sometimes it can be interpreted as repeated subtraction. ...

The following division methods are all based on the form where:

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

Slow Division

Slow division methods are all based on a standard recurence equation: P_{j + 1} = RP_j − q_{n − (j + 1)}D where:

 Pj = the partial remainder of the division R = the radix qn − (j + 1) = the digit of the quotient in position n-j+1 (the position numbers begin with 0 and are numbered from least-significant (0) to most significant (n-1) n = number of digits in the quotient D = the denominator 

Restoring Division

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

1. N < D
2. 1 > N,D > = 1 / 2

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

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

 P[0] = N i=0 while(i<n) { TP[i+1] = 2P*[i] - D if(TP[i] > 0) q[n-(i+1)] = 1; P[i+1] = TP[i+1] if(TP[i] <= 0) q[n-(i+1)] = 0; P[i+1] = TP[i+1] + D i++ } 

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) { if(P[i] >= 0) q[n-(i+1)] = 1; P[i+1] = 2*P[i] - D if(P[j] < 0) q[n-(i+1)] = -1; P[i+1] = 2*P[i] + D i++ } 

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}:  Steps: 1. Mask the negative term:  2. Form the Two's complement of N:  3. Form the positive term:  4. Sum  and :  

Twos complement is the most popular method of signifying negative integers in computer science. ...

SRT Division

Named for its creators (Sweeny, Robertson, and Toker), 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 cause by an incorrectly coded lookup table.

Fast Division

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. In numerical analysis, Newtons method (or the Newton-Raphson method) is an efficient algorithm for finding approximations to the zeros (or roots) of a real-valued function. ...

 The steps of Newton-Raphson are: 

1. Calculate an estimate for the reciprocal of the divisor (D): X₀
2. Compute successively more accurate estimates of the reciprocal: (X₁...X_{i − 1}...X_k)
3. Compute the quotient by multiplying the dividend by the reciprocal of the divisor: Q = NX_k

Assuming the divisor is scaled so .5 < D < 1, the initial estimate for the reciprocal of the divisor is:

 X0 = 2.914 − 2D 

Successively more accurate estimates of the reciprocal can be calculated using:

 Xi + 1 = Xi(2 − DXi) 

Goldschmidt Division

Goldschmidt uses series expansion to converge to the quotient. The strategy of Goldschmidt is repeatedly multiply the dividend and divisor by a factor F to converge the divisor to 1 as the dividend converges to the quotient Q: As the degree of the taylor series rises, it approaches the correct function. ...

 The steps for Goldschmidt are: 

1. Calculate an estimate for the muliply factor F.
2. Multiply the dividend and divisor by F.
3. Loop to step 1.

Assuming the divisor is scaled so 0.9 < = D < = 1.1, the first factor is:

 Fi + 1 = 2 − Di 

Multiplying the dividend and divisor by the factor yields:

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