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