A division algorithm is an algorithm which, given two integers N and D (respectively the numerator and the denominator), computes their quotient and/or remainder, the result of Euclidean 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 algorithms fall into this category.
Variants of these algorithms allow using fast multiplication algorithms. It results that, for large integers, the computer time needed for a division is the same, up to a constant factor, as the time needed for a multiplication, whichever multiplication algorithm is used.
Discussion will refer to the form , where N = numerator (dividend) D = denominator (divisor) is the input, and Q = quotient R = remainder
is the output.
Division by repeated subtraction The simplest division algorithm, historically incorporated into a greatest common divisor algorithm presented in Euclid's Elements, Book VII, Proposition 1, finds the remainder given two positive integers using only subtractions and comparisons:
function divide_unsigned(N, D) if D = 0 then error(DivisionByZero) end R := N Q := 0 while R ≥ D do R := R − D Q := Q + 1 end return (Q, R) end
The proof that the quotient and remainder exist and are unique (described at Euclidean division) gives rise to a complete division algorithm, applicable to both negative and positive numbers, using additions, subtractions, and comparisons:
function divide(N, D) if D = 0 then error(DivisionByZero) end if D < 0 then (Q, R) := divide(N, −D) return (−Q, R) end if N < 0 then (Q, R) := divide(−N, D) if R = 0 then return (−Q, 0) else -- Example: N = -7, D = 3 -- divide(-N, D) = divide(7, 3) = (2, 1) -- R ≠ 0, so return (-2 - 1, 3 - 1) = (-3, 2) -- Check: (-3)*3 + 2 = -7 return (−Q − 1, D − R) end end -- At this point, N ≥ 0 and D > 0 return divide_unsigned(N, D) 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 (being an output-sensitive algorithm), and can serve as an executable specification.
Alternative implementation
An alternative implementation increments a remainder and resets it when it reaches the divisor.
For , the algorithm computes such that , with :
Consider this code in Python: def divide_unsigned2(numerator: int, denominator: int) -> tuple[int, int] quotient: int = 0 remainder: int = 0 for _ in range(numerator): remainder += 1 if remainder == denominator: quotient += 1 remainder = 0 return quotient, remainder
Notes Special cases are and.Compare: in procedure divide_unsigned, denominator must be strictly positive. Variable quotient is never read. So when its assignments highlighted are removed from the code and quotient is removed from the output list, divide_unsigned2, like divide_unsigned, still will compute .
Alternative implementation as counter machine A simple counter machine (CM) can be based on the alternative implementation. The CM instructions are Z (n): Replace rn by 0. S (n): Add 1 to rn. J (m, n, q): If rm = rn, jump to the qth instruction; otherwise go on to the next instruction in the program. The counter machine program is 1: J(1,5,0) 2: S(4) 3: J(4,2,6) 4: S(5) 5: J(0,0,1) 6: S(3) 7: Z(4) 8: S(5) 9: J(0,0,1)
After the CM finishes the computation on initial register values R1=N, R2=D (remaining registers = 0), register R3 holds the (integer part of the) quotient of the division N/D, and register R4 holds the remainder.
Long division
Long division is the standard algorithm used for pen-and-paper division of multi-digit 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 the digit level) at each stage; the multiples then become the digits of the quotient, and the final difference is then the remainder.
When used with a binary radix, this method forms the basis for the (unsigned) integer division with remainder algorithm below. Short division is an abbreviated form of long division suitable for one-digit divisors. Chunking also known as the partial quotients method or the hangman method is a less-efficient form of long division which may be easier to understand. By allowing one to subtract more multiples than what one currently has at each stage, a more freeform variant of long division can be developed as well.
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. In the following pseudo-code, all values are treated as unsigned integers.
if D = 0 then error(DivisionByZeroException) end Q := 0 -- Initialize quotient and remainder to zero R := 0 for i := n − 1 .. 0 do -- Where n is number of bits in N 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
Example If we take N=11002 (1210) and D=1002 (410)
Step 1: Set R=0 and Q=0 Step 2: Take i=3 (one less than the number of bits in N) Step 3: R=00 (left shifted by 1) Step 4: R=01 (setting R(0) to N(i)) Step 5: R < D, so skip statement
Step 2: Set i=2 Step 3: R=010 Step 4: R=011 Step 5: R < D, statement skipped
Step 2: Set i=1 Step 3: R=0110 Step 4: R=0110 Step 5: R>=D, statement entered Step 5b: R=10 (R−D) Step 5c: Q=10 (setting Q(i) to 1)
Step 2: Set i=0 Step 3: R=100 Step 4: R=100 Step 5: R>=D, statement entered Step 5b: R=0 (R−D) Step 5c: Q=11 (setting Q(i) to 1)
end Q=112 (310) and R=0.
Slow division methods Slow division methods are all based on a standard recurrence equation
where: Rj is the j-th partial remainder of the division (R(0) := N(i) step is included) B is the radix (base, usually 2 internally in computers and calculators) q n − (j + 1) is 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 is number of digits in the quotient D is the divisor
Restoring division Restoring division operates on fixed-point fractional numbers and depends on the assumption 0 < D < N.
The quotient digits q are formed from the digit set {0,1}.
The basic algorithm for binary (radix 2) restoring division is:
R := N D := D << n -- R and D need twice the word width of N and Q for i := n − 1 .. 0 do -- For example 31..0 for 32 bits R := 2 * R − D -- Trial subtraction from shifted value (multiplication by 2 is a shift in binary representation) if R >= 0 then q(i) := 1 -- Result-bit 1 else q(i) := 0 -- Result-bit 0 R := R + D -- New partial remainder is (restored) shifted value end end
-- Where: N = numerator, D = denominator, n = #bits, R = partial remainder, q(i) = bit #i of quotient
Non-performing restoring division is similar to restoring division except that the value of 2R is saved, so D does not need to be added back in for the case of R < 0.
Non-restoring division Non-restoring division uses the digit set {−1, 1} for the quotient digits instead of {0, 1}. The algorithm is more complex, but has the advantage when implemented in hardware that there is only one decision and addition/subtraction per quotient bit; there is no restoring step after the subtraction, which potentially cuts down the numbers of operations by up to half and lets it be executed faster. The basic algorithm for binary (radix 2) non-restoring division of non-negative numbers is:
-- Inputs: N (Numerator), D (Denominator) -- n = number of bits -- R and D are usually stored in registers of width 2n or similar to handle shifts
R := N -- Initialize Remainder
for i = n − 1 .. 0 do -- for example 31..0 for 32 bits -- Shift Remainder Left (Algebraically: 2 * R) if R >= 0 then R := 2 * R - D; -- Subtract D q(i) := 1; -- Record quotient bit as 1 else R := 2 * R + D; -- Add D (restore) q(i) := -1; -- Record quotient bit as -1 end if end for
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}: Start: 1. Form the positive term: 2. Mask the negative term: 3. Subtract: :
If the −1 digits of are stored as zeros (0) as is common, then is and computing is trivial: perform a ones' complement (bit by bit complement) on the original . Q := Q − bit.bnot(Q) -- Appropriate if −1 digits in Q are represented as zeros as is common.
Finally, quotients computed by this algorithm are always odd, and the remainder in R is in the range −D ≤ R < D. For example, 5 / 2 = 3 R −1. To convert to a positive remainder, do a single restoring step after Q is converted from non-standard form to standard form: if R < 0 then Q := Q − 1 R := R + D -- Needed only if the remainder is of interest. end if
The actual remainder is R >> n. (As with restoring division, the low-order bits of R are used up at the same rate as bits of the quotient Q are produced, and it is common to use a single shift register for both.)
SRT division SRT division is a popular method for division in many microprocessor implementations. The algorithm is named after D. W. Sweeney of IBM, James E. Robertson of University of Illinois, and K. D. Tocher of Imperial College London. They all developed the algorithm independently at approximately the same time (published in February 1957, September 1958, and January 1958 respectively).
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 most significant difference is that a redundant representation is used for the quotient. For example, when implementing radix-4 SRT division, each quotient digit is chosen from five possibilities: −2, −1, 0, +1, or +2. Because of this, the choice of a quotient digit need not be perfect; later quotient digits can correct for slight errors. (For example, the quotient digit pairs (0, +2) and (1, −2) are equivalent, since .) This tolerance allows quotient digits to be selected using only a few most-significant bits of the dividend and divisor, rather than requiring a full-width subtraction. This simplification in turn allows a radix higher than 2 to be used.
Like non-restoring division, the final steps are a final full-width subtraction to resolve the last quotient bit, and conversion of the quotient to standard binary form.
The original Intel Pentium processor's infamous floating-point division bug was caused by an incorrectly coded lookup table. Pentium processors used a 2048-cell table, of which 1066 cells were to be populated, and values from five cells were mistakenly omitted.
Fast division methods Newton–Raphson division Newton–Raphson uses Newton's method to find the reciprocal of and multiply that reciprocal by to find the
The steps of Newton–Raphson division are: Calculate an estimate for the reciprocal of the divisor . Compute successively more accurate estimates of the reciprocal. This is where one employs the Newton–Raphson method as such. Compute the quotient by multiplying the dividend by the reciprocal of the divisor: .