Skip to navigation

BBC Micro Elite

Shift-and-subtract division

The main algorithm behind Elite's many division routines
References: TIS1, TIS2, DVID4
  Elite implements division in routines like TIS2 using the shift-and-subtract
  algorithm. This is similar in concept to the shift-and-add algorithm used to
  implement multiplication in routines like MULT1, but it's essentially the
  reverse of that algorithm.
  In the same way that shift-and-add implements a binary version of the manual
  long multiplication process, shift-and-subtract implements long division. We
  shift bits out of the left end of the number being divided (A), subtracting
  the largest possible multiple of the divisor (Q) after each shift; each bit of
  A where we can subtract Q gives a 1 the answer to the division, otherwise it
  gives a 0.
  In pseudo-code, the algorithm to calculate T = P / Q (with remainder A) looks
  like this:
    T = 0
    A = 0
    for x = 7 to 0
      A = A << 1
      A(bit 0) = P(bit x)
      if A >= Q then
        A = A − Q
        T(bit x) = 1
  This is the algorithm implemented in TIS2, except we save space (and make
  things much more confusing) by using A for both the number being divided and
  the remainder, building the answer in T instead of P, and using set bits in T
  to implement the loop counter. The basic idea of shifting and subtracting is
  the same, though.