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←