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?