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 ← {+⌿1 0⌽0 10⊤⍵}⍣≡ ⍝ decimal digit vector normalisation.
)
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