Binary Division by Shift and Subtract

Basically the reverse of the mutliply by shift and add.

 

 

  • Set quotient to 0
  • Align leftmost digits in dividend and divisor
  • Repeat
    • If that portion of the dividend above the divisor is greater than or equal to the divisor
      • Then subtract divisor from that portion of the dividend and
      • Concatentate 1 to the right hand end of the quotient
      • Else concatentate 0 to the right hand end of the quotient
    • Shift the divisor one place right
  • Until dividend is less than the divisor
  • quotient is correct, dividend is remainder
  • STOP

FURTHER EXAMPLE


QUESTION:

What is the average number of operations needed to complete each of these algorithms, assuming the dividend has m digits in the representation and the divisor has n digits?

ADVANCED CONSIDERATION:

Modify this algorithm to produce the fractional part of the quotient.

Check out the tutorial section and get more help on-line (click here).

[Prev][TOC]


Last updated 2000/05/15
© J.A.N. Lee, 2000.