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 base^{N}+-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:

- Ternary divide by 2 example
- Decimal divide by 9 example

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 Base^{N}+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).

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

Note that a "trit" (below) is a "**tr**inary dig**it**,
just as a "bit" is a "**b**inary dig**it**".

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.

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

- Miscellaneous section
- Utah Logic home page
- Back to Back to Philosophy Department
- University of Utah home page

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