```Integer Long Division
---------------------
The  long division algorithm for bta and sba is roughly the same as that used by
a  (hand-cranked  or  electro-)  mechanical calculator. The method dates back to
Charles Babbage's Analytical Engine; see below.

Three  odometer-style "registers" [p], [q] and [r] are required, together with a
shifting mechanism (s) attached to register [q].

[p]  and [q] hold the dividend and divisor respectively; [r] the result; and (s)
keeps track of how far the divisor [q] has been shifted.

Shift  mechanism  (s)  is  implemented as a simple unary count: |, |<, |<<, ···,
where  '|' is a place holder (unary systems such as the first few Roman numerals
need  such a marker, as they don't have a zero). It could equally well have used
a numeric counter: 0, 1, 2, 3, ···, but both in the mechanical calculator and in
this workspace, the unary method is simpler.

The steps for finding the integer quotient and remainder of two integers, are as
follows:

[0] Clear result register [r].

[1] Align the most significant digit of [q] with that of [p], by shifting [q] to
the left and keeping track with shift mechanism (s).

[2] Repeatedly subtract [q] from [p], adding 1 to result register [r] each time,
until [p] goes negative.

[3] Undo  the  previous subtraction by adding [q] back into [p] and decrementing
[r]  by  1. If [q] is no longer shifted, the division is complete: the final
quotient is in [r] and the remainder in [p]. Otherwise,

[4] Shift [r] one place left; shift [q] one place right; continue from step 2.

Notice  that  the algorithm does not attempt to avert the final superfluous sub-
traction by testing whether [q] is greater than [p] beforehand. This is to avoid
having  to construct a separate comparison mechanism (which would probably be no
quicker  than  the  subtraction)  so only the cost of the subsequent re-addition
would  be  gained  by the extra complexity. Given that (for decimal numbers) the
average number of subtractions is 5, the maximum improvement that such an optim-
isation could deliver would be 20%.

The following example traces the (decimal) division of 1234 by 38 to produce 32,
remainder 18:

Step      [p]       [q](s)    [r]
¯¯¯¯  1 2 3 4       3 8|        ·
[0]   1 2 3 4       3 8|        0
[1]   1 2 3 4     3 8 0|<       0
[1]   1 2 3 4   3 8 0 0|<<      0
[2] - 2 5 6 6   3 8 0 0|<<      1
[3]   1 2 3 4   3 8 0 0|<<      0
[4]   1 2 3 4     3 8 0|<       0
[2]     8 5 4     3 8 0|<       1
[2]     4 7 4     3 8 0|<       2
[2]       9 4     3 8 0|<       3
[2]   - 2 8 6     3 8 0|<       4
[3]       9 4     3 8 0|<       3
[4]       9 4       3 8|      3 0
[2]       5 6       3 8|      3 1
[2]       1 8       3 8|      3 2
[2]     - 2 0       3 8|      3 3
[3]       1 8       3 8|      3 2
│                   │
│                   └── quotient
└────────────────────── remainder

This algorithm is _considerably_ more efficent than the naïve alternative of re-
peated subtraction without a shift:

[0] Clear result register [r].

[1] Repeatedly  subtract [q] from [p], adding 1 to result register [r] each time
until [p] goes negative.

[2] Undo  the  previous subtraction by adding [q] back into [p] and decrementing
[r]  by  1.  The  division is complete: the final quotient is in [r] and the
remainder in [p].

Step      [p]       [q]     [r]
¯¯¯¯  1 2 3 4       3 8       ·
[0]   1 2 3 4       3 8       0
[1]   1 1 9 6       3 8       1
[1]   1 2 5 8       3 8       2
[1]   1 2 2 0       3 8       3
[1]   1 0 8 2       3 8       4
[1]   1 0 4 4       3 8       5
[1]   1 0 0 6       3 8       6
[1]     9 6 8       3 8       7
[1]     9 3 0       3 8       8
[1]     8 9 2       3 8       9
[1]     8 5 4       3 8     1 0
[1]     8 1 6       3 8     1 1
[1]     7 7 8       3 8     1 2
[1]     7 4 0       3 8     1 3
[1]     7 0 2       3 8     1 4
[1]     6 6 4       3 8     1 5
[1]     6 2 6       3 8     1 6
[1]     5 8 8       3 8     1 7
[1]     5 5 0       3 8     1 8
[1]     5 1 2       3 8     1 9
[1]     4 7 4       3 8     2 0
[1]     4 3 6       3 8     2 1
[1]     3 9 8       3 8     2 2
[1]     3 6 0       3 8     2 3
[1]     3 2 2       3 8     2 4
[1]     2 8 4       3 8     2 5
[1]     2 4 6       3 8     2 6
[1]     2 0 8       3 8     2 7
[1]     1 7 0       3 8     2 8
[1]     1 3 2       3 8     2 9
[1]       9 4       3 8     2 0
[1]       5 6       3 8     3 1
[1]       1 8       3 8     3 2
[1]     - 2 0       3 8     3 3
[2]       1 8       3 8     3 2
│                 │
│                 └──── quotient
└────────────────────── remainder

The second (inefficient) algorithm takes O(p÷q) steps, whereas the first (effic-
ient) one takes only O(5×10⍟p÷q). As an extreme example, dividing 1,000,000 by 1
would take a million steps using the slow algorithm, but only a little more than
sixty using the fast one.

In  "The  Cog  Wheel  Brain",  Doron Swade makes the following observation about
Charles Babbage's Analytical Engine, which was designed in the first half of the
nineteenth century:

"The  pursuit  of the "shadowy vision" unfolded between summer 1834 and 1836. In
bursts of  intense  activity Babbage imparted to his new Engine a succession of
features at which one can only marvel. He devised the first automatic mechanism
for direct multiplication and division. The process of division was particular-
ly daunting, and he remarked that of the arithmetical operations of the machine
"none certainly offered more formidable difficulties".

For division he designed the Engine to operate in an exploratory way. The mach-
ine performs an operation, examines the result, and takes an appropriate action
depending  on  the outcome. Specifically, the mechanism for division performs a
series  of tentative subtractions until the result goes negative. The detection
of the minus sign indicates that there has been one too many, and the next step
is  to restore the correct number by an addition. The result is then multiplied
by ten and the process of repeated subtraction is repeated. By keeping count of
how  many  subtractions  are executed at each stage before the sign change, the
digits of the result of the division are generated in turn."

See: ##.sba ##.bta ##.roman

Back to: →Implementation_Details←
```