Utah p implies necessarily possible p

Division by just in time subtraction

LeRoy Eide has presented some work on balanced ternary at various meetings. (Although the most current presentation seems to be at: http://www.dyalog.com/dfnsdws/n_JitSub.htm) Among the interesting results are his algorithms for efficient division by 2, 4, 8, 10. Since these results generalize to division in any base by the baseN+-1, there has been intermittant interest in them, and no published paper. Since they were first presented at the meetings, this seems a logical place to document them until such time (if ever) he formally publishes them.

The term "just in time subtraction" was coined by Dylan Pocock.

Note that the algorithm returns the answer LEAST significant digit first, and has the same running time as a subtraction if there is no remainder, and two subtractions if there is a remainder. (And can be used as a one subtraction time test for divisiblity. (Suitable for hardware implimentation.) It has been pointed out that it could be used for a hardware fast divide by ten on binary computers by using it as a "divide by 5" followed by a shift.

What follows is a crude transcription of the notes John Halleck took at a meeting, and are used here with his (and LeRoy Eide's) permission, and includes two examples:

Discussion

There is a straight forward extension that computes integer quotient and remainder (in two subtactions) if you don't have exact multiples of 9 lying around.

You can divide by BaseN+1 by noticing that (for example in base 10) 11x-10x=1x

In base three this gives efficient algorithms for divide by 2, 4, 8, and 10 (amoung others).

In general you have efficient versions of divide for, (Base^N)+-1 (N positive and integer).


Ternary divide by 2 example

The balanced ternary example uses 0 for 0, + for 1, and - for -1

Note that a "trit" (below) is a "trinary digit, just as a "bit" is a "binary digit".

 We have  2x    (For  example (12 = + + 0)
 We want   x
   One way of finding x, given 2x, is to subtract 2x from 3x (3x-2x=x)
  (Or alternately, we could add a negative 2x.)


But, of course we don't have x (since that is what we want to find) and
so we don't know 3x.

HOWEVER, we do know one thing about it...  Namely that it has a  low order
zero digit. (Since whatever it was, we introduced the zero by shifting it
left.)

    We have 2X =  + + 0   (12), and we want to divide by two.
       so  -2X =  - - 0

  So, what we know is:

    3x = ? ? ? ? 0
 + -2x = 0 0 - - 0
------------------
 =   x = ? ? ? ? ?

    But we CAN fill in the rightmost bit of x, since this is an
    addition problem, and we have both low order digits.

    3x = ? ? ? ? 0
 + -2x = 0 0 - - 0
------------------
 =   x = ? ? ? ? 0

    But now we know the low order trit of x, we therefore know the
    next to the low order trit of 3x, since it is identical. (Since
    3x is x shifted left one trit.)

    3x = ? ? ? 0 0
 + -2x = 0 0 - - 0
------------------
 =   x = ? ? ? ? 0

 
    But now the second column is a straight forward addition problem
    ( 0 plus -) and we can compute the second digit (-). and fill that
    digit in for x, and the same knowledge in 3x.


    3x = ? ? - 0 0
 + -2x = 0 0 - - 0
------------------
 =   x = ? ? ? - 0

   And, lo, we can now do the arithmetic to compute the next digit.
   (and a carry this time.)

(carry) =   -
    3x  = ? + - 0 0
 + -2x  = 0 0 - - 0
------------------
 =   x  = ? ? + - 0

   And the next...

    3x  = ? + - 0 0
 + -2x  = 0 0 - - 0
------------------
 =   x  = ? 0 + - 0

   And so on.

    3x  = 0 + - 0 0
 + -2x  = 0 0 - - 0
------------------
 =   x  = 0 0 + - 0

  And we have our answer.

Decimal divide by 9 example.

Some people are more comfortable working in decimal, and the algorithm generalizes to decimal nicely, so we'll present a decimal example.

Assume in decimal that we have a multiple of 9, and we want to divide it by 9.

For example, let us take 9x = 1332.

We are, of course, looking for 1x.

LeRoy points out that 1x = 10x - 9x, so we could get x by subtracting our
known 9x from 10x.

Ah... I hear you think...  we don't happen to know 10x either.

True, but we know something about it, namely that it ends in a zero...

OK, let's set this up.

10x = ? ? ? 0
-9x = 1 3 3 2
=============
  x = ? ? ? ?

We actually have enough information to compute the last column:



borrows:    -1

   10x = ? ? ? 0
   -9x = 1 3 3 2
   =============
     x = ? ? ? 8

But if the last digit of x is 8, then the next to last digit of 10x must be 8. 

borrows:    -1    
   10x = ? ? 8 0
   -9x = 1 3 3 2
   =============
     x = ? ? ? 8

And we have enough information to compute the next digit of x (and therefore
 the next digit of 10x)

borrows:    -1
   10x = ? 4 8 0
   -9x = 1 3 3 2
   =============
     x = ? ? 4 8

And now we have enough to compute the next digit.

borrows:    -1
   10x = 1 4 8 0
   -9x = 1 3 3 2
   =============
     x = ? 1 4 8

and so on.

borrows:    -1
   10x = 1 4 8 0
   -9x = 1 3 3 2
   =============
     x = 0 1 4 8



Go to ...


This page is http://web.utah.edu/utahlogic/misc/justintime.html
This page was last modified on January 26th, 2009.