# Why Does The Division Alorithim Need [Register Size] + 1 Iterations

Following this flow diagram for division hardware I made a program to "simulate" division on $$N^+$$.

# 4 bit version
def div(dividend, divisor)
quotient = 0
remainder = dividend
divisor <<= 4

for i in 1..5
remainder -= divisor
if remainder >= 0
quotient <<= 1
quotient |= 1
else
remainder += divisor
quotient <<= 1
end
divisor >>= 1
end

return quotient
end


What I don't understand is why there needs to be an "extra" iteration of the loop. If the divisor is being shifted down the register by 1, and the register is say 64 bits, then it would take 64 iterations to clear the register. Or in my case 4. However without that extra step the algorithm does not produce the correct result. Why is that?

• Can you create a Minimal, Complete, and Verifiable example? In fact, what I am asking is just a call that looks like div(125,7) that needs that extra iteration of the loop. Also, forgive me if I am slow or inattentive, but which line of code do you mean by that "extra" iteration of the loop? – John L. Oct 22 '18 at 17:10
• @Apass.Jack That's what the code is for? It is ruby code that can be placed at the interpreter. I am asking about the for i in 1..5 instead of for i in 1..4 – grant2088 Dec 4 '18 at 7:45

Because divisor <<= 4 means original_divisor * (2**4), where I use original_divisor to denote the value of divisor when you began computing div(dividend, divisor).
Every time you do divisor >>= 1, you divide that divisor by 2. So you will get original_divisor * (2**3), original_divisor * (2**2), original_divisor * (2**1), original_divisor * (2**0).
Notice there are 5 of them, corresponding to original_divisor times $$2^4, 2^3, 2^2, 2^1, 2^0$$ respectively or 16,8,4,2,1 respectively. You should have noticed how 4 is changed to 5 by now. There are 4 possible shifts to the left, by 4 bits, by 3 bits, by 2 bits and by 1 bit. There is also a non-shift, or shift by 0 bit.