1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Apass.Jack Oct 22 '18 at 17:10
  • $\begingroup$ @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 $\endgroup$ – grant2088 Dec 4 '18 at 7:45
1
$\begingroup$

"Why is that?"

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.

What you have experienced is the most famous/infamous error in computer programming, off-by-one error or off-by-one errors. I must have made this error hundreds if not thousands of times.

Just in case you have not heard of the most famous joke in computer programming, here it is. "There are two hard things in computer science: cache invalidation, naming things, and off-by-one errors." Or a shorter version, "There are two kinds of errors, off by one errors".

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.