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←