Close

Counting

A project log for Ternary Computing Menagerie

A place for documenting the many algorithms, data types, logic diagrams, etc. that would be necessary for the design of a ternary processor.

mechanical-advantageMechanical Advantage 04/13/2019 at 07:590 Comments

Counting in balanced ternary is just as straightforward as any other positional number system, but the unusual symbols used take some getting used to.

Following is the notation for counting two digits up from zero:

01234
000++-+0++

And here is the notation for counting down from zero:

0-1-2-3-4
000--+-0--

Notice how the negative equivalent of each positive number has the -'s and +'s reversed? That's all it takes to turn a negative into a positive or a positive into a negative. The 0's remain the same. Negatives and positives are direct complements. Also notice that the number zero has no sign. It is it's own complement and there is no need to do additional computation to prevent having two zero's (negative and positive) like you do in 2's complement binary.

Incrementing consists of changing the least significant trit like so:   -  => 0 => + => -
Decrementing consists of changing the least significant trit like so: + => 0 => -  => +

When you transition from a plus value to a minus value or vice versa, a carry over to the next least significant trit is generated which has the opposite value of the least significant trits new value.

Another point to take into account is the number of values possible for a given number of trits. In binary, all numbers are positive so if you have 8 bits you get all 8 bits worth, making 256 values. With the use of 2's complement you gain the same number of values in the negative range minus one giving you 255 more values. The total becomes 511 possible values. 2's complement adds complexity to addition and subtraction circuits and requires some additional computations when you are dealing with signed numbers, but it does double the available number of values. It trades away some speed and simplicity for capacity.

Balanced ternary doesn't require this trade off for more capacity as the negative values come natively, but it means that for each negative value, you aren't getting another positive value. Let's see how this compares.

# of digitsBinary PositivesTernary PositivesTernary All Values
1213
2449
381327
4164081
532121243
664364729
71281,0932,187
82563,2806,561
95129,84119,683

As you can see, it's not even close. The number of positives available in balanced ternary is more than an order of magnitude greater by the time you get to 9 trits but for those 9 trits you also get the same number of negative values "for free" without the need for addional computations or circuitry.

However, all is not perfectly well in this arrangement. Nowadays we are quite used to using the 8 bit byte, the 2-byte hexadecimal group, and the 32 or 64 bit word that progress naturally as powers of 2. Let's look at the values for these common sizes we are all familiar with as well as some powers of 3 to get a comparison.

# of DigitsBinary PositivesTernary PositivesTernary All Values
82563,2806,561
95129,84119,683
1665,53621,523,36043,046,721
271.3E+083.8E+127.6E+12
324.3E+099.3E+141.9E+15
641.8E+191.7E+303.4E+30
812.4E+242.2E+384.4E+38

Ideally, a modern balanced ternary system would have capacity exceeding that of a modern binary system so that no additional rearrangement would be necessary to work with data coming from binary systems. Further, it would be optimal if the positive values alone exceeded a 64 bit system. As we can see above, the 27 trit systems positive values would exceed that of a 32 bit system, but not a 64 bit system. The next power of three above 27 is 81 which far exceeds anything in common use today, but would be almost comically over-engineered.

In order to moderate back to something more realistic it would be necessary to drop the insistance on using powers of the base and just settle for a multiple of the base. Here is a more reasonable arrangement:

# of DigitsBinary PositivesTernary PositivesTernary All Values
324.3E+099.3E+141.9E+15
424.4E+125.5E+191.1E+20
453.5E+131.5E+213.0E+21
641.8E+191.7E+303.4E+30

42 trits would do the trick, but a 45 trit system would likely be favorable because it is not just divisible by 3, but also by 9. a 9 trit number is a convenient analog to 8 bits and is still a small enough number of digits that you can wrap your head around it manually.

There are a few other odds and ends about ternary digits that deserve a quick note.

You can tell which numbers are divisible by three by the number of zero-valued least signinficant trits.
+++0 is divisible by 3
++00 is divisible by 9
+000 is divisible by 27
etc...

Dividing by three is as simple as right-shifting, just like right-shifting to divide by two in binary. As long as the trit being shifted off is a zero, there is no remainder.

Detecting even from odd is not as straightforward as in binary where any number with a 0 in the least significant position is even. In balanced ternary, even numbers have an even number of non-zero trits and odd numbers have an odd number of non-zero trits. This takes a bit more work but now you have a comparatively easy way to determine if something is divisible by any power of 3 as well as if something is divisible by 2. I haven't fully hashed out how this would be beneficial, but it seems like it should be able to simplify division a bit. For example, if a number fails both of the above tests, it is a prime number larger than 3. If a number passes both tests it is also divisible by six (2 x 3). Again, this is not really developed, but is promising for fast integer division.

Discussions