Fast BT division-by-2 using "Just-in-Time Subtraction" (LeRoy Eide) ------------------------------------------------------------------- John Halleck provides this description of LeRoy Eide's very nifty algorithm for balanced ternary division-by-2. Notice that the algorithm is unusual in that it generates digits of the result from least- to most-significant (right-to-left). This is based on work originally presented at the Utah Logic Group. See: http://web.utah.edu/utahlogic The method is best illustrated using the more familar base-10 and division by 9. LeRoy points out that q = (10×q)-9×q, so we could get q by subtracting our known 9×q from 10×q. Ah... I hear you think... we don't happen to know 10×q either. True, but we know something about it, namely that it ends in a zero ... For example, suppose we want to divide 1332 by 9 to find quotient q, so that 1332 = 9×q. OK, let's set this up: 10q = . . . 0 -9q = 1 3 3 2 ================= q = . . . . We actually have enough information to compute the last column: ¯1 ← borrow 10q = . . . 0 -9q = 1 3 3 2 ================= q = . . . 8 But if the last digit of q is 8, then the next to last digit of 10×q must also be 8. ¯1 10q = . . 8 0 -9q = 1 3 3 2 ================= q = . . . 8 And we have enough information to compute the next digit of q (and therefore the next digit of 10×q) 10q = . 4 8 0 -9q = 1 3 3 2 ================= q = . . 4 8 And now we have enough to compute the next digit of q and 10×q: 10q = 1 4 8 0 -9q = 1 3 3 2 ================= q = . 1 4 8 And we're done! 10q = 1 4 8 0 -9q = 1 3 3 2 ================= q = 0 1 4 8 Observations ------------ The method clearly extends to: 1. Division by 99, 999, ... ¯1+10*⍵. 2. Division by base+1 (rather than base-1) 3. Number bases other than 10 (including balanced ternary). In the case of balanced ternary numbers, this gives us fast division by 2, 4, 8 and 10 (among others). Balanced Ternary Division by 2 ------------------------------ Here is John's worked example for balanced ternary numbers: Suppose we want BT: 1 1 0 (decimal 12) divided by 2. To subtract a balanced ternary number, we just add its negation: We have 2q = 1 1 0 so -2q = ¯1 ¯1 0 Then the steps are similar to the decimal example above: 3q = . . . . 0 + -2q = 0 0 ¯1 ¯1 0 =================== q = . . . . . We can fill in the rightmost digit of q, since this is an addition problem, and we have both low order digits: 3q = . . . . 0 + -2q = 0 0 ¯1 ¯1 0 =================== q = . . . . 0 But now we know the low order digit of q, we therefore know the next to the low order digit of 3q, since it is identical. (since 3q is q shifted left by one). 3q = . . . 0 0 + -2q = 0 0 ¯1 ¯1 0 =================== q = . . . . 0 Now the second column is a straightforward addition problem (0 plus ¯1) and we can compute the second digit (¯1) and fill that digit in for q, and the same knowledge in 3q: 3q = . . ¯1 0 0 + -2q = 0 0 ¯1 ¯1 0 =================== q = . . . ¯1 0 And, lo, we can now do the arithmetic to compute the next digit (with a carry this time). ¯1 ← carry 3q = . 1 ¯1 0 0 + -2q = 0 0 ¯1 ¯1 0 =================== q = . . 1 ¯1 0 And the next ... ¯1 3q = . 1 ¯1 0 0 + -2q = 0 0 ¯1 ¯1 0 =================== q = . 0 1 ¯1 0 And so on. 3q = 0 1 ¯1 0 0 + -2q = 0 0 ¯1 ¯1 0 =================== q = 0 0 1 ¯1 0 And we have our answer. But what if there's a remainder? -------------------------------- On the face of it, the method seems to run into a problem if the dividend is not an exact multiple of the divisor. But we can fix it. The effect is that the difference between (base-1) and the remainder is sub- tracted from _each_ digit position, so we can recover this as it falls off the left side of the result and add it back, vector-wise, to each column. Then, all that remains to do is to normalise any columns that have overflowed (≥base). LeRoy points out that an alternative approach for balanced ternary division by 2 is to start by subtracting its parity (2|) from the dividend, rendering it even and thus divisible by 2 without remainder. The <parity> of a BT number is: if the number has only a single digit (¯1 0 1), then its absolute value; otherwise, the <parity> of the (BT) sum of its digits. See →bt← for more on this. Coding in D ----------- Here is a D-coding for decimal (base-10) fast division by 9 with remainder. The method suggests a right-to-left reduction, which deduces a digit at a time into an accumulating argument: ↑scan/... If no remainder pops out of the left side of the reduction, we're done: rem=0: ... Otherwise, we add the remainder to each column (rem+rslt) and normalise (carry overflows forward) the result in a second reduction: ↑norm/... Remember that LeRoy's just-in-time subtraction method (conveniently) operates right-to-left, in contrast with traditional left-to-right division. decimal_div_9←{ ⍝ Fast decimal division-by-9 - LeRoy Eide. scan←{(enc-⍺-+/2↑⍵),1↓⍵} ⍝ pair-wise deduction of digits. nlz←{(-1⌈+/∨\0≠⍵)↑⍵} ⍝ without superfluous leading zeros. enc←0 10∘⊤ ⍝ 2-digit decimal encode. rslt←1↓↑scan/0,⍵,0 ⍝ remainder, quotient. rem←9|9-1↑rslt ⍝ remainder. rem=0:(nlz rslt)rem ⍝ exact divide: quotient and 0-remainder. norm←{(⍺ 0+enc ⍬⍴⍵),1↓⍵} ⍝ pair-wise overflow resolution. rslt←1↓↑norm/0,rem+rslt ⍝ vector-sum of rem with each digit. (nlz rslt)rem ⍝ integer quotient and remainder. } div9 1 2 3 4 5 ⍝ 12345÷9 → 1371r6 ┌───────┬─┐ │1 3 7 1│6│ └───────┴─┘ ( While in keeping with its surroundings, the normalisation code is less than optimal. Rather than digit-by-digit reduction, it would be faster to use a parallel shift-carry function: norm←{ ⍝ decimal digit overflow normalisation. 10∧.>⍵:⍵ ⍝ all digits in range 0..9: done. ∇ +⌿1 0⌽0 10⊤⍵ ⍝ otherwise: shift-carry-add and try again. } Note that from Dyalog V11, this could be coded using a fixpoint function derived from the power operator ⍣: norm ← {+⌿1 0⌽0 10⊤⍵}⍣≡ ⍝ decimal digit vector normalisation. or: norm ← +⌿∘(1 0∘⌽)∘(0 10∘)⍣≡ ⍝ decimal digit vector normalisation. ) ⍝ see →tacit← Balanced Ternary ---------------- To change our decimal division-by-9 function to balanced ternary division-by-2, we need change only the encode function (enc) and divisor (9). This suggests abstracting an operator, which takes these as left and right operands ⍺⍺ and ⍵⍵: fast_div←{ ⍝ Fast division by ⍵⍵ - LeRoy Eide. scan←{(enc-⍺-+/2↑⍵),1↓⍵} ⍝ pair-wise deduction of digits. nlz←{(-1⌈+/∨\0≠⍵)↑⍵} ⍝ without superfluous leading zeros. enc←⍺⍺ ⍝ 2-digit encode. rslt←1↓↑scan/0,⍵,0 ⍝ remainder, quotient. rem←⍵⍵|⍵⍵-1↑rslt ⍝ remainder. rem=0:(nlz rslt)rem ⍝ exact divide: quotient and 0-remainder. norm←{(⍺ 0+enc ⍬⍴⍵),1↓⍵} ⍝ pair-wise overflow resolution. rslt←1↓↑norm/0,rem+rslt ⍝ vector-sum of rem with each digit. (nlz rslt)rem ⍝ integer quotient and remainder. } We are now in a position to derive functions for decimal_division_by_9 and bal- anced_ternary_division_by 2: enc_dec ← 0 10∘⊤ ⍝ 2-digit decimal encode. dec_div_9 ← enc_dec fast_div 9 ⍝ decimal divide-by-9. ⍝ dec_div_9 1 2 3 4 5 ⍝ decimal 12345÷9 → 1371r6 ┌───────┬─┐ │1 3 7 1│6│ └───────┴─┘ enc_bt ← {¯1+0 3⊤3⊥1+0 3⊤⍵} ⍝ 2-digit balanced ternary encode. bt_div_2 ← enc_bt fast_div 2 ⍝ bt divide-by-2. ⍝ __ _ _ bt_div_2 1 0 ¯1 ¯1 ⍝ balanced ternary 1011÷11 → 111r1 ┌──────┬─┐ │1 1 ¯1│1│ └──────┴─┘ See also: ratrep ratsum bt tacit Back to Balanced Ternary Arithmetic: →bt← Back to: contents Back to: Workspaces