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.

```