Balanced ternary is a non-standard positional numeral system

Non-standard positional numeral systems

Non-standard positional numeral systems here designates numeral systems that may be denoted positional systems, but that deviate in one way or another from the following description of standard positional systems:...

 (a balanced form

Signed-digit representation

Signed-digit representation of numbers indicates that digits can be prefixed with a − sign to indicate that they are negative.Signed-digit representation can be used in low-level software and hardware to accomplish fast addition of integers because it can eliminate carries...

), useful for comparison logic. It is a ternary

Ternary numeral system

Ternary is the base- numeral system. Analogous to a bit, a ternary digit is a trit . One trit contains \log_2 3 bits of information...

 system, but unlike the standard (unbalanced) ternary system, the digits have 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 can represent all integers without resorting to a separate minus sign.

Balanced ternary is counted as follows. (In this example, the symbol 1 denotes the digit −1, but alternatively for easier parsing "−" may be used to denote −1 and "+" to denote +1.)

Balanced ternary

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 (the string of 1s must be the same length, so if the result of the addition has more digits, subtract nothing from these extra digits). For example, 021₃ + 111₃ = 202₃, 202₃ − 111₃ = 111_3(bal) = 7₁₀.

Computation

There were a few experimental Russian computers, Setun

Setun

Setun was a balanced ternary computer developed in 1958 at Moscow State University. The device was built under the lead of Sergei Sobolev and Nikolay Brusentsov. It was the only modern ternary computer, using three-valued ternary logic instead of two-valued binary logic prevalent in computers...

, in the early days of computing that were built with balanced ternary instead of binary. The notation has a number of computational advantages over regular binary, and over traditional ternary. Particularly, the one-digit multiplication table

Multiplication table

In mathematics, a multiplication table is a mathematical table used to define a multiplication operation for an algebraic system....

 has no carries in balanced ternary, and the addition table has only two symmetric carries instead of three.

This notation has the property that 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.

Other 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 (60₁₀ = 11110) will be balanced perfectly with an 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. It is too cumbersome for practical use, however.

Similarly, a currency system using ternary values 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.

Fractional balanced ternary

Balanced ternary can be extended to fractional numbers similarly to how decimal numbers are written past the decimal point

Decimal separator

Different symbols have been and are used for the decimal mark. The choice of symbol for the decimal mark affects the choice of symbol for the thousands separator used in digit grouping. Consequently the latter is treated in this article as well....

.http://www.abhijit.info/tristate/tristate.html For instance, ⅓ is 0.1 and ⅔ is 1.1.

Donald Knuth

Donald Knuth

Donald Ervin Knuth is a computer scientist and Professor Emeritus at Stanford University.He is the author of the seminal multi-volume work The Art of Computer Programming. Knuth has been called the "father" of the analysis of algorithms...

 has pointed out that truncation and rounding are the same operation in balanced ternary — they produce exactly the same result. Moreover, there is no ambiguity in rounding (a property shared with other odd bases) since the number ½ is represented by the repeating fraction 0.1 (and 1.1).

Unlike in standard base notation, where integer values and terminating fractions have multiple representations (e.g. in decimal, ¼ = 0.25₁₀ = 0.249₁₀), in balanced ternary such numbers have only one representation (¼ = 0.11_3(bal)). On the other hand, numbers half of a terminating fraction (i.e. whose denominator is 2 times a power of 3) do have multiple representations e.g. ⅙ = 0.01_3(bal) = 0.11_3(bal).

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).

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:

EWLINE Multiplication × − 0 + − + 0 − 0 0 0 0 + − 0 +

EWLINE Addition + − 0 + − − + − 0 0 − 0 + + 0 + + −

External links

• Development of ternary computers at Moscow State University
• Nikolay Brusentsov
• Representation of Fractional Numbers in Balanced Ternary
• “Third base”, ternary and balanced ternary number systems
• Complete bibliography of all works done on Balanced Ternary through history
• The Balanced Ternary Number System (includes decimal integer to balanced ternary converter)
• The binomial triangle reduced to balanced ternary lists. OEIS
• Balanced (Signed) Ternary Notation by Brian J. Shelburne (PDF file)
• The ternary calculating machine of Thomas Fowler by Mark Glusker