CODEWITHSUNDEEP
algorithmbinarydivisioninteger-division
notaorb
notaorb

Reputation: 2180

Integer Division Algorithm: question on Wiki version

Wiki says this following algorithm is a version of long division. Does anyone know mathematically what is happening R is being left shifted, then the least significant bit of R(0) is set to the N(i)?

I know the left shift is 2R, but I'm a little lost after that.

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

Upvotes: 2

Views: 118

Answers (1)

MBo
MBo

Reputation: 80197

Essentially it is the same algorithm as we learnt in school for "division by corner" (various notation in different countries, I show "Eurasia" one)

_176 |3_
 15   58
---   
 _26
  24
 ---   
   2

We put the most significant digit of dividend (1) into (temporary) remainder and check if it is larger than divisor. 1<3, so we virtually put 0 into quotient and make remainder 17 - this is 1*10 + 7, in binary R := R << 1; R(0) := N(i)

17>3, so we subtract product of divisor and max possible digit of quotient. Here 3*5, we put 5 into quotient, in binary version digit of quotient in case of R ≥ D is 1 (Q(i) := 1)

At the second step we multiply remainder 2 by 10 and add the next digit 6. In binary version equivalent is R := R << 1; R(0) := N(i) and so on.

Upvotes: 1

Related Questions