Algorithm --------- We are doing integer division of two positive numbers. Refer to the Patterson and Hennessey book on page 202. The terminology for the pieces of data are Dividend ---------- = Quotient + Remainder Divisor and we will find the Quotient and Remainder for a given Dividend and Divisor. We use Divisor, Quotient, and Remainder frequently, and will represent these as D, Q, and R, respectively. After step 0, we do not reference Dividend. We will use twice the precision, i.e. since this example has n bit values, we will find a Quotient and Remainder of 2n bits each. (When done, we can put the Quotient back as n bits) An important note is that the divisor extends to 2n bits and starts with the original n bits in the upper part. 0. R = Remainder = Dividend = 00..0 01001010 // shown for example with n=8 D = Divisor = 00001000 00..0 Q = Quotient = 00..0 00..0 count = 0 (decimal) MAXcount = n+1 (decimal), i.e. number of bits plus 1. 1. R = R - D 2. If R >= 0 Q = left shift(Q) Q(0) = 1 else R = R + D, // correct the R value Q = left shift(Q) Q(0) = 0 3. D = right shift (D) 4. count++ count = 1 if count < MAXcount, goto 1 At the end, R is the remainder, Q is the quotient