Ternary Computing Menagerie

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:

0	1	2	3	4
00	0+	+-	+0	++

And here is the notation for counting down from zero:

0	-1	-2	-3	-4
00	0-	-+	-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 digits	Binary Positives	Ternary Positives	Ternary All Values
1	2	1	3
2	4	4	9
3	8	13	27
4	16	40	81
5	32	121	243
6	64	364	729
7	128	1,093	2,187
8	256	3,280	6,561
9	512	9,841	19,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 Digits	Binary Positives	Ternary Positives	Ternary All Values
8	256	3,280	6,561
9	512	9,841	19,683
16	65,536	21,523,360	43,046,721
27	1.3E+08	3.8E+12	7.6E+12
32	4.3E+09	9.3E+14	1.9E+15
64	1.8E+19	1.7E+30	3.4E+30
81	2.4E+24	2.2E+38	4.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 Digits	Binary Positives	Ternary Positives	Ternary All Values
32	4.3E+09	9.3E+14	1.9E+15
42	4.4E+12	5.5E+19	1.1E+20
45	3.5E+13	1.5E+21	3.0E+21
64	1.8E+19	1.7E+30	3.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.

---

A binary digit is a bit, a ternary digit is a trit.

The number of possible values that can be represented by x number of digits in a number system with base n is n^x. For example:

# of digits	Base-2 values	Base-3 values
1	2	3
2	4	9
3	8	27
4	16	81
5	32	243
6	64	729
7	128	2,187
8	256	6,561

As you can see, a ternary system triples the number of possible values with each additional trit whereas the binary system doubles.

The balanced ternary numbering system is a positional numbering system where the position of each digit determines its relative magnitude. Numbers further to the left have greater magnitude and numbers further to the right have lesser magnitude.

Here is a decimal example and a ternary (unbalanced) example:

Decimal:                     841 = (8*100) + (4*10) + (1*1) = Eight hundred and forty-one

Unbalanced Ternary: 201 = (2*9)    + (0*3)  + (1*1)  = Nineteen

One facet of positional numbering that is so obvious it is unlikely to be noted is that they count upwards from zero. This is quite natural and, in fact, cannot be otherwise in most cases unless you add a sign to indicate that the number is negative and you are counting down from zero.

This is not particularly interesting until you take into account the term "balanced". Unlike other systems in common use, balanced ternary has an odd-numbered base. This makes possible an arrangement that cannot be done with any even-numbered base like binary, decimal, etc. Because there is an odd number of possible values, you can arrange them such that they fall on both sides of zero. In other words, the digit in each position may be either negative or positive. The three possible values for a given trit are -1, 0, and 1. Negative one is denoted with "-", one is denoted with "+" and a zero with "0".

Let's look at our previous examples compared to balanced ternary:
Decimal:                     841 = (8*100) + (4*10) + (1*1) = Eight hundred and forty-one
Unbalanced Ternary: 201 = (2*9)   + (0*3)  + (1*1) = Nineteen
Balanced Ternary:     -+0 = (-1*9)  + (1*3) 0 (0*1)  = Negative six

Notice that we were able to represent a negative number without a negative sign. The sign of the number overall is the sign of the most significant (leftmost) trit. In balanced ternary, all numbers are natively signed or unsigned without recourse to specialized systems such as 2's-complement or sign-magnitude.

Here are a few more examples:

-0+0   = (-1*27) + (0*9)   + (1*3)  + (0*1) = -24
0++-   = (0*27)  + (1*9)    + (1*3)  + (-1*1) = 11
+---     = (1*27)   + (-1*9)   + (-1*3) + (-1*1) = 14
00-0  = (0*27)  + (0*9)  + (-1*3)  + (0*1) = -3
++++   = (1*27)   + (1*9)   + (1*3)   + (1*1) = 40
0000 = (0*27)  + (0*9)  + (0*3)  + (0*1) = 0
----      = (-1*27)  + (-1*9)  + (-1*3) + (-1*1) = -40

Each post will be, to the degree possible, narrowly targeted to a specific small aspect of computer science as it relates to a hypothetical balanced ternary environment. Hence, the use of the term "menagerie" in the title of the project. The goal is to make an easily searchable collection of topics in one place that can serve as a reference for others.

I will begin with several posts on very elementary points that could easily be found with a quick internet search. Regardless, I will include posts for them in this project for the sake of completeness.

Following that I will take up various subjects including, but not limited to:
Balanced ternary numbering
History of ternary systems
Single input ternary gates
Double input ternary gates
Gate naming conventions
Counting
Functional completeness
flip-flap-flops
primitive data types
gray codes
parity calculations
error detection circuits
tritwise operators
trit-masks
status flags and status registers
adders and subtractors
floating point numbers
... and so on

Some of this work is already done but needs to be compiled for easy readability.