Balanced ternary

Let \mathcal{D}_{3} := \lbrace \operatorname{T}, 0, 1 \rbrace denote the set of symbols (also called glyphs or characters), where the symbol \bar{1} is sometimes used in place of \operatorname{T}. Define an integer-valued function f = f_{\mathcal{D}_{3}} : \mathcal{D}_{3} \to \mathbb{Z} by :\begin{align} f_{}(\operatorname{T}) &= -1, \\ f_{}(0) &= 0, \\ f_{}(1) &= 1, \end{align} where the right hand sides are integers with their usual values. This function, f_{}, is what rigorously and formally establishes how integer values are assigned to the symbols/glyphs in \mathcal{D}_{3}. One benefit of this formalism is that the definition of "the integers" (however they may be defined) is not conflated with any particular system for writing/representing them; in this way, these two distinct (albeit closely related) concepts are kept separate. The set \mathcal{D}_{3} together with the function f_{} forms a balanced signed-digit representation called the balanced ternary system. It can be used to represent integers and real numbers. Ternary integer evaluation Let \mathcal{D}_{3}^{+} be the Kleene plus of \mathcal{D}_{3}, which is the set of all finite length concatenated strings d_n \ldots d_0 of one or more symbols (called its digits) where n is a non-negative integer and all n + 1 digits d_n, \ldots, d_0 are taken from \mathcal{D}_{3} = \lbrace \operatorname{T}, 0, 1 \rbrace. The start of d_n \ldots d_0 is the symbol d_0 (at the right), its end is d_n (at the left), and its length is n + 1. The ternary evaluation is the function v = v_{3} ~:~ \mathcal{D}_{3}^{+} \to \mathbb{Z} defined by assigning to every string d_n \ldots d_0 \in \mathcal{D}_{3}^{+} the integer :v\left( d_n \ldots d_0 \right) ~=~ \sum_{i=0}^{n} f_{} \left( d_{i} \right) 3^{i}. The string d_n \ldots d_0 represents (with respect to v) the integer v\left( d_n \ldots d_0 \right). The value v\left( d_n \ldots d_0 \right) may alternatively be denoted by {d_n \ldots d_0}_{\operatorname{bal}3}. The map v : \mathcal{D}_{3}^{+} \to \mathbb{Z} is surjective but not injective since, for example, 0 = v(0) = v(00) = v(0 0 0) = \cdots. However, every nonzero integer has exactly one representation under v that does not end (on the left) with the symbol 0, i.e. d_n = 0 . If d_n \ldots d_0 \in \mathcal{D}_{3}^{+} and n > 0 then v satisfies: :v\left( d_n d_{n-1} \ldots d_0 \right) ~=~ f_{} \left( d_{n} \right) 3^{n} + v\left( d_{n-1} \ldots d_0 \right) which shows that v satisfies a sort of recurrence relation. This recurrence relation has the initial condition v\left( \varepsilon \right) = 0 where \varepsilon is the empty string. This implies that for every string d_n \ldots d_0 \in \mathcal{D}_{3}^{+}, :v\left( 0 d_n \ldots d_0 \right) = v\left( d_n \ldots d_0 \right) which in words says that leading 0 symbols (to the left in a string with 2 or more symbols) do not affect the resulting value. The following examples illustrate how some values of v can be computed, where (as before) all integer are written in decimal (base 10) and all elements of \mathcal{D}_{3}^{+} are just symbols. :\begin{alignat}{10} v\left( \operatorname{T} \operatorname{T} \right) &= && f_{}\left( \operatorname{T} \right) 3^{1} + && f_{}\left( \operatorname{T} \right) 3^{0} &&= &&(-1) &&3 &&\,+\, &&(-1) &&1 &&= -4 \\ v\left( \operatorname{T} 1 \right) &= && f_{}\left( \operatorname{T} \right) 3^{1} + && f_{}\left( 1 \right) 3^{0} &&= &&(-1) &&3 &&\,+\, &&(1) &&1 &&= -2 \\ v\left( 1 \operatorname{T} \right) &= && f_{}\left( 1 \right) 3^{1} + && f_{}\left( \operatorname{T} \right) 3^{0} &&= &&(1) &&3 &&\,+\, &&(-1) &&1 &&= 2 \\ v\left( 1 1 \right) &= && f_{}\left( 1 \right) 3^{1} + && f_{}\left( 1 \right) 3^{0} &&= &&(1) &&3 &&\,+\, &&(1) &&1 &&= 4 \\ v\left( 1 \operatorname{T} 0 \right) &= f_{}\left( 1 \right) 3^{2} + && f_{}\left( \operatorname{T} \right) 3^{1} + && f_{}\left( 0 \right) 3^{0} &&= (1) 9 \,+\, &&(-1) &&3 &&\,+\, &&(0) &&1 &&= 6 \\ v\left( 1 0 \operatorname{T} \right) &= f_{}\left( 1 \right) 3^{2} + && f_{}\left( 0 \right) 3^{1} + && f_{}\left( \operatorname{T} \right) 3^{0} &&= (1) 9 \,+\, &&(0) &&3 &&\,+\, &&(-1) &&1 &&= 8 \\ \end{alignat} and using the above recurrence relation :v\left( 1 0 1 \operatorname{T} \right) = f_{}\left( 1 \right) 3^{3} + v\left( 0 1 \operatorname{T} \right) = (1) 27 + v\left( 1 \operatorname{T} \right) = 27 + 2 = 29. == Conversions to/from other representations ==

Conversion to decimal In the balanced ternary system the value of a digit n places left of the radix point is the product of the digit and 3n. This is useful when converting between decimal and balanced ternary. In the following the strings denoting balanced ternary carry the suffix, bal3. For instance, : 10bal3 = 1 × 31 + 0 × 30 = 3dec : 10𝖳bal3 = 1 × 32 + 0 × 31 + (−1) × 30 = 8dec : −9dec = −1 × 32 + 0 × 31 + 0 × 30 = 𝖳00bal3 : 8dec = 1 × 32 + 0 × 31 + (−1) × 30 = 10𝖳bal3 Similarly, the first place to the right of the radix point holds 3−1 = , the second place holds 3−2 = , and so on. For instance, : −dec = −1 + = −1 × 30 + 1 × 3−1 = 𝖳.1bal3. An integer is divisible by three if and only if the digit in the units place is zero. We may check the parity of a balanced ternary integer by checking the parity of the sum of all trits. This sum has the same parity as the integer itself. Balanced ternary can also be extended to fractional numbers similar to how decimal numbers are written to the right of the radix point. : In decimal or binary, integer values and terminating fractions have multiple representations. For example, = 0.1 = 0.1 = 0.0. And, = 0.12 = 0.12 = 0.02. Some balanced ternary fractions have multiple representations too. For example, = 0.1bal3 = 0.0bal3. Certainly, in the decimal and binary, we may omit the rightmost trailing infinite 0s after the radix point and gain a representations of integer or terminating fraction. But, in balanced ternary, we can't omit the rightmost trailing infinite −1s after the radix point in order to gain a representations of integer or terminating fraction. Donald Knuth As a result, if these two representations are used for balanced and unsigned ternary numbers, an unsigned n-trit positive ternary value can be converted to balanced form by adding the bias b and a positive balanced number can be converted to unsigned form by subtracting the bias b. Furthermore, if x and y are balanced numbers, their balanced sum is when computed using conventional unsigned ternary arithmetic. Similarly, if x and y are conventional unsigned ternary numbers, their sum is when computed using balanced ternary arithmetic. Conversion from any integer base to balanced ternary We may convert to balanced ternary with the following formula: : \left(a_na_{n-1}\cdots a_1a_0.c_1 c_2 c_3\cdots\right)_b = \sum_{k=0}^n a_kb^k + \sum_{k=1}^\infty c_kb^{-k}. where, : anan−1...a1a0.c1c2c3... is the original representation in the original numeral system. : b is the original radix. b is 10 if converting from decimal. : ak and ck are the digits k places to the left and right of the radix point respectively. For instance, −25.4dec = −(1T×1011 + 1TT×1010 + 11×101−1) = −(1T×1011 + 1TT×1010 + 11×101T) = −(1T×101 + 1TT + 11×0.) = −(1T1T + 1TT + 0.) = −10T1. = T01T. 1010.12 = 1T10 + 1T1 + 1T−1 = 1T10 + 1T1 + 1TT = 10T + 1T + 0. = 101. == Addition, subtraction and multiplication and division ==

The single-trit addition, subtraction, multiplication and division tables are shown below. For subtraction and division, which are not commutative, the first operand is given to the left of the table, while the second is given at the top. For instance, the answer to 1 − T = 1T is found in the bottom left corner of the subtraction table. : : : : Multi-trit addition and subtraction Multi-trit addition and subtraction is analogous to that of binary and decimal. Add and subtract trit by trit, and add the carry appropriately. For example: 1TT1TT.1TT1 1TT1TT.1TT1 1TT1TT.1TT1 1TT1TT.1TT1 + 11T1.T − 11T1.T − 11T1.T → + TT1T.1 ______________ ______________ _______________ 1T0T10.0TT1 1T1001.TTT1 1T1001.TTT1 + 1T + T T1 + T T1 ______________ ________________ ________________ 1T1110.0TT1 1110TT.TTT1 1110TT.TTT1 + T + T 1 + T 1 ______________ ________________ ________________ 1T0110.0TT1 1100T.TTT1 1100T.TTT1 Multi-trit multiplication Multi-trit multiplication is analogous to that of binary and decimal. 1TT1.TT × T11T.1 _____________ 1TT.1TT multiply 1 T11T.11 multiply T 1TT1T.T multiply 1 1TT1TT multiply 1 T11T11 multiply T _____________ 0T0000T.10T Multi-trit division Balanced ternary division is analogous to that of binary and decimal. However, 0.5dec = 0.1111...bal3 or 1.TTTT...bal3. If the dividend is over the plus or minus half divisor, the trit of the quotient must be 1 or T. If the dividend is between the plus and minus of half the divisor, the trit of the quotient is 0. The magnitude of the dividend must be compared with that of half the divisor before setting the quotient trit. For example, 1TT1.TT quotient 0.5 × divisor T01.0 _____________ divisor T11T.1 ) T0000T.10T dividend T11T1 T000 10T0, set T _______ 111T 1TT1T 111T > 10T0, set T _______ T00.1 T11T.1 T001 10T0, set T ________ 1T.T1T 1T.T1T 1TT1T > 10T0, set T ________ 0 Another example, 1TTT 0.5 × divisor 1T _______ Divisor 11 )1T01T 1T = 1T, but 1T.01 > 1T, set 1 11 _____ T10 T10 1T, set 1 11 _____ 1 T1 < 1 < 1T, set 0 ___ 1T 1T = 1T, trits end, set 1.TTTTTTTTT... or 0.111111111... In balanced ternary, there is a simpler division method that does not require comparing the remainders and operates directly according to the rules. This method originated from Donald Knuth trial quotient method, but this method is not perfect. Later, it was improved by other scholars, completely abandoning the judgment of semi-closed intervals and instead using the condition of whether the highest bit of the remainder of each round of division is 0 to determine whether the round of division is over, and named it the double trial quotient method: the core logic is to split the dividend into two vectors (p and s), where the number of digits of p is at most the same as the divisor q, and s is the vector of the remaining digits; then according to the rule (double positive or double negative gives a positive quotient, one positive and one negative gives a negative quotient, and the others are 0), the quotient is subtracted at most once or twice in each round of division. If the highest bit of the remainder p is still not 0 after subtraction once, it needs to be subtracted again. If the highest bit of the remainder p is 0, the round of division is over, and the bit is the double quotient. The value is doubled and the result is given to register r; then the remainder p Shift left one bit, discard the highest bit of the previous round's divisor (already 0), pull one bit of s to supplement it, and get the new remainder p to carry on to the next round. The result r (3 times magnified) is shifted right one bit and supplemented with 0. Then, when s is exhausted, the result r and the dividend p constitute the final quotient and remainder. + ++0- ++ _____________ _______ +0- )+0++0+ +- )+0+ -0+ -+ ____________ ______ 0+-+ 0++ -0+ -+ ____________ ______ 00-0 +- 000 -+ ____________ ______ -0+ 0 +0- ____________ Add 0+ and ++ ,quotient get +-- 0 ==Square roots and cube roots==

The process of extracting the square root in balanced ternary is analogous to that in decimal or binary. :(10\cdot x+y)^{\mathrm{1T}}-100\cdot x^{\mathrm{1T}}=\mathrm{1T0}\cdot x\cdot y+y^{\mathrm{1T}}= \begin{cases} \mathrm{T10}\cdot x+1, & y=\mathrm{T} \\ 0, & y=0 \\ \mathrm{1T0}\cdot x+1, & y=1 \end{cases} As in division, we should check the value of half the divisor first. For example, 1. 1 1 T 1 T T 0 0 ... _________________________ √ 1T 10.10, set 1 1T0 −1.T0 ________ 11×10=110 1T0T 1T0T>110, set 1 10T0 −10T0 ________ 111×10=1110 T1T0T T1T0T111T0, set 1 10T110 −10T110 __________ 111T1×10=111T10 TT1TT0T TT1TT0T(10\cdot x+y)^{10}-1000\cdot x^{10}=1000\cdot x^{\mathrm{1T}}\cdot y+100\cdot x\cdot y^{\mathrm{1T}}+y^{10}= \begin{cases} \mathrm{T000}\cdot x^{\mathrm{1T}}+100\cdot x+\mathrm{T}, & y=\mathrm{T}\\ 0, & y=0\\ 1000\cdot x^{\mathrm{1T}}+100\cdot x+1, & y=1 \end{cases} Like division, we should check the value of half the divisor first too. For example: 1. 1 T 1 0 ... _____________________ ¹⁰√ 1T − 1 11TT, set 1 1×1×1000+1=1001 −1.001 __________ T0T000 11×100 − 1100 borrow 100×, do division _________ 10T000 TT1T00 TT1T001T1T01TT, set 1 11T×11T×1000+1=11111001 − 11111001 ______________ 1T10T000 11T1×100 − 11T100 borrow 100×, do division __________ 10T0T01TT 1T0T0T00 T01010T11dec = bal3 = 1.259921dec = 1.1T1 000 111 001 T01 00T 1T1 T10 111bal3. ==Irrational numbers==

As in any other integer base, algebraic irrationals and transcendental numbers do not terminate or repeat. For example: : The balanced ternary expansions of \pi is given in OEIS as , that of e in . == Applications ==

In computer design In the early days of computing, a few experimental Soviet computers were built with balanced ternary instead of binary, the most famous being the Setun, built by Nikolay Brusentsov and Sergei Sobolev. The notation has a number of computational advantages over traditional binary and ternary. Particularly, the plus–minus consistency cuts down the carry rate in multi-digit multiplication, and the rounding–truncation equivalence cuts down the carry rate in rounding on fractions. In balanced ternary, the one-digit multiplication table remains one-digit and has no carry and the addition table has only two carries out of nine entries, compared to unbalanced ternary with one and three respectively. Knuth wrote that "Perhaps the symmetric properties and simple arithmetic of this number system will prove to be quite important some day," Balanced ternary may also provide a more natural representation for the qutrit and quantum computing systems that use it. Other applications The theorem that every integer has a unique representation in balanced ternary was used by Leonhard Euler to justify the identity of formal power series :\prod_{n=0}^{\infty} \left(x^{-3^n}+1+x^{3^n}\right)=\sum_{n=-\infty}^{\infty}x^n. Balanced ternary has other applications besides computing. For example, a classical two-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 (60dec = 1T1T0bal3) 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. Similarly, consider a currency system with coins worth 1¤, 3¤, 9¤, 27¤, 81¤. If the buyer and the seller each have only one of each kind of coin, any transaction up to 121¤ is possible. For example, if the price is 7¤ (7dec = 1T1bal3), the buyer pays 1¤ + 9¤ and receives 3¤ in change. ==See also==