Balanced ternary
Balanced ternary is a ternary numeral system (i.e. base 3 with three digits) that uses a balanced signed-digit representation of the integers in which the digits have the values −1, 0, and 1. This stands in contrast to the standard (unbalanced) ternary system, in which digits have values 0, 1 and 2. The balanced ternary system can represent all integers without using a separate minus sign; the value of the leading non-zero digit of a number has the sign of the number itself. The balanced ternary system is an example of a non-standard positional numeral  system. It was used in some early computers and also in some solutions of balance puzzles. Different sources use different glyphs used to represent the three digits in balanced ternary. In this article, T (which resembles a ligature of the minus sign and 1) represents −1, while 0 and 1 represent themselves. Other conventions include using '−' and '+' to represent −1 and 1 respectively, or using Greek letter theta (Θ), which resembles a minus sign in a circle, to represent −1. In publications about the Setun computer, −1 is represented as overturned 1: "". Balanced ternary makes an early appearance  in Michael Stifel's book "Arithmetica Integra" (1544). It also occurs in the works of Johannes Kepler and Léon Lalanne. Related signed-digit schemes in other bases have been discussed by John Colson, John Leslie, Augustin-Louis Cauchy, and possibly even the ancient Indian Vedas. Definition. Let formula_1 denote the set of symbols (also called glyphs or characters) formula_2, where the symbol formula_3 is sometimes used in place of formula_4 Define an integer-valued function formula_5 by where the right hand sides are integers with their usual (decimal) values. This function, formula_9 is what rigorously and formally establishes how integer  values are assigned to the symbols/glyphs in formula_10 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 formula_1 together with the function formula_12 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 formula_13 be the Kleene plus of formula_1, which is the set of all finite length concatenated strings  formula_15 of one or more symbols (called its digits) where formula_16 is a non-negative integer and all formula_17 digits formula_18 are taken from formula_19 The start of formula_15 is the symbol formula_21 (at the right), its end is formula_22 (at the left), and its length is formula_17. The ternary evaluation is the function formula_24 defined by assigning to every string formula_25 the integer The string formula_15 represents (with respect to formula_28) the integer formula_29 The value formula_30 may alternatively be denoted by formula_31 The map formula_32 is surjective but not injective since, for example, formula_33 However, every integer has  exactly one representation under formula_28 that does not end (on the left) with the symbol formula_35 i.e. formula_36 If formula_25 and formula_38 then formula_28 satisfies: which shows that formula_28 satisfies a sort of recurrence relation. This recurrence relation has the initial condition formula_42 where formula_43 is the empty string. This implies that for every string formula_44 which in words says that leading formula_46 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 formula_28 can be computed, where (as before) all integer are written  in decimal (base 10) and all elements of formula_13 are just symbols. and using the above recurrence relation 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 3. This is useful when converting between decimal and balanced ternary. In the following the strings denoting balanced ternary carry the suffix, "bal3". For instance, Similarly, the first place to the right of the radix point holds 3 = , the second place holds 3 = , and so on. For instance, 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.1 = 0.1 = 0.0. Some balanced ternary fractions have multiple representations  too. For example, = 0.1 = 0.0. 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 has pointed out that truncation and rounding are the same operation in balanced ternary—they produce exactly the same result (a property shared with other balanced numeral systems). The number is not exceptional; it has two  equally valid representations, and two equally valid truncations: 0. (round to 0, and truncate to 0) and 1. (round to 1, and truncate to 1). With an odd radix, double rounding is also equivalent to directly rounding to the final precision, unlike with an even radix. The basic operations—addition, subtraction, multiplication, and division—are done as in regular ternary. Multiplication by two can be done by adding a number to itself, or subtracting itself after a-trit-left-shifting. An arithmetic shift left of a balanced ternary number is the equivalent of multiplication by a (positive, integral) power of  3; and an arithmetic shift right of a balanced ternary number is the equivalent of division by a (positive, integral) power of 3. Conversion to and from a fraction. The conversion of a repeating balanced ternary number to a fraction is analogous to converting a repeating decimal. For example (because of 111111 = ()): 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 formula_52 is given in OEIS as , that of formula_53 in . Conversion from ternary. Unbalanced ternary can be converted to balanced ternary notation  in two ways: If the three values of ternary logic are "false", "unknown" and "true", and these are mapped to balanced ternary as T, 0 and 1 and to conventional unsigned ternary values as 0, 1 and 2, then balanced ternary can be viewed as a biased number system analogous to the offset binary system. If the ternary number has "n" trits, then the bias "b" is which is represented as all ones in either conventional or biased form. 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 to balanced ternary from any integer base. We may convert to balanced ternary with the following formula: where, For instance, 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: Multi-trit multiplication. Multi-trit multiplication is analogous to that of binary and decimal. Multi-trit  division. Balanced ternary division is analogous to that of binary and decimal. However, 0.5 = 0.1111... or 1.TTTT... If the dividend 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, Another example, Another example, Square roots and cube roots. The process of extracting the square root in balanced ternary is analogous  to that in decimal or binary. As in division, we should check the value of half the divisor first. For example, Extraction of the cube root in balanced ternary is similarly analogous to extraction in decimal or binary: Like division, we should check the value of half the divisor first too. For example: Hence = 1.259921 = 1.1T1 000 111 001 T01 00T 1T1 T10 111. 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. "The complexity of arithmetic circuitry for balanced ternary arithmetic is not much greater than it is for the binary system , and a given number requires only formula_58 as many digit positions for its representation.""Perhaps the symmetric properties and simple arithmetic of this number system will prove to be quite important some day." 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 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 (60 = 1T1T0) 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¤ (7 = 1T1), the buyer pays 1¤ + 9¤ and receives 3¤ in change. They may also provide a more natural representation for the qutrit and systems that use it.