Ternary
Categories: Numeration | Computer arithmetic | Positional numeral systems
Ternary is the base-3 numeral system. Ternary digits are known as trits (trinary digit), analogous to bit. This system is also known as trinary.
Although ternary most often refers to a system in which the three digits, 0, 1 and 2, are all nonnegative integers, the adjective also lends its name to the balanced ternary system, useful for comparison logic.
Contents |
Ternary computers
See also: ternary logic
Balanced ternary notation
A number system called balanced ternary uses digits with the values −1, 0, and 1. This combination is especially valuable for ordinal relationships between two values, where the three possible relationships are less-than, equals, and greater-than. Balanced ternary is counted as follows. (In this example, the symbol 1 denotes the digit −1, but alternatively for easier parsing "−" may be used denote −1 and "+" to denote +1.)
| Decimal | −6 | −5 | −4 | −3 | −2 | −1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Balanced ternary | 110 | 111 | 11 | 10 | 11 | 1 | 0 | 1 | 11 | 10 | 11 | 111 | 110 |
Unbalanced ternary can be converted to balanced ternary notation by adding 1111.. with carry, then subtracting 1111... without borrow. For example, 0213 + 1113 = 2023, 2023 − 1113 = 1113(bal) = 710.
Balanced ternary is easily represented as electronic signals, as potential can either be negative, neutral, or positive. Utilizing a third state encompasses more data per digit; linearly approximately log(3)/log(2)=~1.589 bits per trit.
Applications
Balanced ternary has other applications besides computing. For example, a classical "2-pan" balance, with one weight for each power of 3, can weigh relatively heavy objects accurately with a small number of weights, by moving weights between the two pans and the table. For example, with weights for each power of 3 through 81, a 60-gram object (6010 = 11110) will be balanced perfectly with a 81 gram weight in the other pan, the 27 gram weight in its own pan, the 9 gram weight in the other pan, the 3 gram weight in its own pan, and the 1 gram weight set aside. This is an optimal solution in terms of the number of weights needed to weigh any object.
Similarly, a currency system using balanced ternary would save visits to the bank - customers would be likely to have exact change, or be able to get a small number of coins in change, and sellers would just occasionally need to deposit a large coin or two. The system works by representing positive values as coins the customer gives the merchant, and negative values as coins the merchant gives the customer. For example, if a merchant sells an item for five zorkmids, the customer would give the merchant a nine-zorkmid coin, and the merchant would give the customer a three-zorkmid coin and a one-zorkmid coin.
Computation
There were a few unsuccessful Russian computers in the early days of computing that were built with balanced ternary instead of binary, and the notation has a number of computational advantages. For example, the one-digit multiplication table has no carries in balanced ternary, and the addition table has only two symmetric carries instead of the three of regular ternary.
This notation has the leading non-zero digit is the sign of the full number. To compare two numbers, simply compare digits from the most significant to the least significant. The direction of the magnitude compare of the first digits that are different is the direction of the magnitude compare of the full numbers.
A number is divisible by three if the last digit is zero. The quick test for even is the analog of the base ten divide-by-nine test: add up all the digits and repeat until you have a one-digit number; the number is even if the final sum is zero.
Donald Knuth has pointed out that truncation and rounding are the same operation—they produce exactly the same result.
The basic operations—addition, subtraction, multiplication, and division—are done as in regular ternary, except that there are some special considerations on the size compare. Multiply 2 by 10 in ternary and then divide the result by 2 to see the issue. The intermediate results are the same (in reverse order) in the two cases, and so you can use one as a check on the other.
Digit shifts multiply or divide by three instead of by two as in binary.
Multiplication by two can be done by adding a number to itself. Division by two can be done with the same operation count as an add by LeRoy Eide's algorithm (an algorithm that returns the result least significant digit first, instead of most significant digit first as standard division).
A generalization of LeRoy Eide's algorithm provides fast (same overhead as an add) algorithms for division by any number of the form (3^n +- 1). (Which includes fast divide algorithms for the popular numbers 2, 4, 8, and 10 [among others])
As in binary, there are balanced ternary equivalents of shift and add multiplication, and shift and multiply exponentiation algorithms.
A common convention for balanced ternary is to represent the digits by "+" for +1, "−" for −1, and "0" for zero. Using this convention, the multiplication and addition tables are:
|
|
Comparison to Other Radixes
Compared to base 10 and 2
| Decimal | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| Binary | 0 | 1 | 10 | 11 | 100 | 101 | 110 | 111 | 1000 | 1001 | 1010 |
| Ternary | 0 | 1 | 2 | 10 | 11 | 12 | 20 | 21 | 22 | 100 | 101 |
Compact ternary representation: base 9 and 27
Ternary is inefficient for human usage, just as binary is. Therefore, nonary (base 9, each digit is two ternary digits) or base 27 (each digit is three ternary digits) is often used, similar to how octal and hexadecimal systems are used in place of binary. Ternary also has a unit similar to a byte, the tryte, which is six ternary digits.
- See Septemvigesimal