Balanced ternary
Balanced ternary is a ternary numeral system that represents integers using the digits −1, 0, and +1 (often denoted as 1̅, 0, and 1 or N, 0, P), where each digit is a coefficient for a power of 3, allowing unique encoding of both positive and negative numbers without a separate sign bit.[1][2] Early descriptions of balanced ternary and related signed-digit systems appeared in the 18th and 19th centuries, including John Colson's 1726 essay on "negativo-affirmative arithmetick" and John Leslie's 1820 work, but the system gained practical application through Thomas Fowler's 1840 wooden ternary calculating machine, which used balanced ternary for arithmetic operations.[1][3][4] In the 20th century, it was implemented in the Soviet Setun computer, developed at Moscow State University in 1958 as the first modern ternary computer, featuring 18-trit words and balanced ternary logic for efficient computation.[5][2] Balanced ternary offers several advantages over binary and standard ternary systems, including simplified negation by inverting digits (changing +1 to −1 and vice versa, leaving 0 unchanged), identical operations for addition and subtraction without borrowing, and reduced carry propagation in arithmetic, making it particularly efficient for certain hardware implementations and puzzles like balance scales.[1][2] Computer scientist Donald Knuth described it as "perhaps the prettiest number system of all" due to these elegant properties in The Art of Computer Programming.[1]Fundamentals
Definition and Digits
Balanced ternary is a ternary numeral system, meaning it uses base 3 as its radix, but employs a set of three symmetric digits: -1, 0, and +1.[6][7] This digit set distinguishes it from standard ternary, which uses 0, 1, and 2, by incorporating negative values directly into the digits rather than relying on a separate sign.[6] The symmetry of the digits—-1, 0, +1—centers the representation around zero, enabling the encoding of both positive and negative integers without an additional sign bit or magnitude adjustment.[8][7] This balance facilitates unique representations for every integer and simplifies certain arithmetic operations by minimizing carry propagation.[9] Historical notations for the digits vary; the value -1 has been denoted as T, −, or an overline (¯1), while +1 is typically 1 and 0 remains 0.[7][2] In positional notation, each digit's place value corresponds to a power of 3, starting with the rightmost position as $3^0 = 1, increasing leftward to higher powers.[9][8] For example, the balanced ternary number $1\bar{1} evaluates to $1 \times 3^1 + (-1) \times 3^0 = 3 - 1 = 2 in decimal.[8]Integer Representation
In balanced ternary, integers are encoded using the digit set \{-1, 0, 1\}, often denoted as T, 0, and 1, where T represents -1.[2] The value of an n+1-digit balanced ternary integer d_n d_{n-1} \dots d_1 d_0 is evaluated as v = \sum_{i=0}^{n} d_i \cdot 3^i, with each d_i \in \{-1, 0, 1\}.[10] This positional system allows direct encoding of both positive and negative integers through the choice of digits, without requiring an explicit sign bit.[11] Every integer has exactly one finite balanced ternary representation, ensuring uniqueness without redundant forms or a separate sign prefix.[11] The canonical form is obtained by excluding leading zeros, which standardizes the representation while preserving this uniqueness.[2] In contrast to standard (unbalanced) ternary, which employs digits {0, 1, 2} and necessitates additional mechanisms like a sign bit for negative numbers, balanced ternary inherently resolves positive/negative ambiguity via the signed digits.[10] Representative examples of small integers in balanced ternary include:| Decimal | Balanced Ternary | Evaluation |
|---|---|---|
| 0 | 0 | $0 \cdot 3^0 |
| 1 | 1 | $1 \cdot 3^0 |
| -1 | T | -1 \cdot 3^0 |
| 2 | 1T | $1 \cdot 3^1 + (-1) \cdot 3^0 = 3 - 1 |
| 3 | 10 | $1 \cdot 3^1 + 0 \cdot 3^0 = 3 |
| 4 | 11 | $1 \cdot 3^1 + 1 \cdot 3^0 = 3 + 1 |
| -2 | T1 | -1 \cdot 3^1 + 1 \cdot 3^0 = -3 + 1 |
| -3 | T0 | -1 \cdot 3^1 + 0 \cdot 3^0 = -3 |
Fractional Representation
In balanced ternary, the representation of fractional numbers extends the positional notation used for integers by incorporating negative powers of 3 to the right of the radix point. The value of a balanced ternary number with both integer and fractional parts is given by the formula \sum_{i=-m}^{n} d_i \cdot 3^i where each digit d_i \in \{-1, 0, 1\} (often denoted as T, 0, 1 for readability), m > 0 is the number of fractional digits, and n \geq 0 is the highest integer power. This allows precise encoding of non-integer values, with the fractional portion contributing terms like d_{-1} \cdot 3^{-1} = d_{-1}/3 and d_{-2} \cdot 3^{-2} = d_{-2}/9.[13] Certain fractions terminate exactly in balanced ternary because their denominators are powers of 3, enabling representation using only a finite number of fractional digits. For instance, $1/3 = 0.1 since $1 \cdot 3^{-1} = 1/3, and $1/9 = 0.01 since $1 \cdot 3^{-2} = 1/9. Similarly, $4/9 = 0.11 as $1 \cdot 3^{-1} + 1 \cdot 3^{-2} = 1/3 + 1/9 = 4/9. These terminating representations arise directly from the base-3 structure, contrasting with binary systems where such fractions often require infinite expansions.[13] Other fractions, such as $1/2, do not terminate and instead repeat periodically. The exact representation is $1/2 = 0.\overline{1} (repeating 1), computed as the infinite geometric series \sum_{k=1}^{\infty} 3^{-k} = (1/3)/(1 - 1/3) = 1/2. An approximation with finite digits, such as truncating to three digits 0.111 = 1/3 + 1/9 + 1/27 = 13/27 ≈ 0.481, illustrates how finite expansions approximate the value, with more digits improving accuracy. Unlike standard ternary, balanced ternary avoids digit 2, ensuring all representations use only symmetric digits around zero.[13] The use of digits \{-1, 0, 1\} provides inherent symmetry in fractional approximations, allowing errors to be evenly distributed around zero without bias toward positive or negative deviations. This property enhances precision in computational applications, as rounding or truncation in balanced ternary equates to nearest-neighbor selection, minimizing average error compared to unsigned systems. For example, in floating-point implementations, an 18-trit mantissa can achieve over 8 decimal digits of precision for fractions due to this balanced encoding.[13]Conversions
To and From Decimal
To convert a balanced ternary number to its decimal equivalent, each digit is multiplied by the corresponding power of 3 based on its position, where the rightmost digit is $3^0 = 1, and the value contributed by a digit + is positive, by - (often denoted as T or ¯1) is negative, and by 0 is zero; the results are then summed.[2][1] For example, the balanced ternary number $1\overline{1}0 (where \overline{1} denotes -1) represents $1 \times 3^2 + (-1) \times 3^1 + 0 \times 3^0 = 9 - 3 + 0 = 6 in decimal.[2] Similarly, $111 in balanced ternary is $1 \times 3^2 + 1 \times 3^1 + 1 \times 3^0 = 9 + 3 + 1 = 13 in decimal.[1] The reverse conversion—from decimal to balanced ternary—involves repeated division of the absolute value by 3, but with adjustment for remainders: if the remainder is 0 or 1, it becomes the digit +0 or +1; if 2, it is recorded as -1 (T) and 1 is added to the quotient for the next step.[2][14] This process continues until the quotient is zero, yielding the digits from least to most significant. For instance, converting 2 to balanced ternary: 2 ÷ 3 = 0 remainder 2 (record T, add 1 to quotient → 1); 1 ÷ 3 = 0 remainder 1 (record 1); result is $1\overline{1}, or 1T, verifying as $1 \times 3^1 + (-1) \times 3^0 = 3 - 1 = 2.[2] For 13: 13 ÷ 3 = 4 remainder 1; 4 ÷ 3 = 1 remainder 1; 1 ÷ 3 = 0 remainder 1; result is 111.[1] Negative numbers are handled inherently through the signed digits, eliminating the need for a separate sign bit or magnitude representation; to negate a balanced ternary number, invert each digit (+ to -, - to +, 0 unchanged).[2][1] For example, the negation of $1\overline{1} (2) is \overline{1}1 (-2), computed as (-1) \times 3^1 + 1 \times 3^0 = -3 + 1 = -2.[2] For fractional parts, the conversion from decimal extends the process to the left of the radix point by repeatedly multiplying the fractional value by 3 and recording the integer part as the next digit, continuing until the desired precision or termination.[2] Conversely, evaluating a balanced ternary fraction to decimal sums the signed digit values multiplied by negative powers of 3. For example, $0.1 in balanced ternary is $1 \times 3^{-1} = \frac{1}{3} \approx 0.333; $0.1 \overline{1} is $1 \times 3^{-1} + (-1) \times 3^{-2} = \frac{1}{3} - \frac{1}{9} = \frac{2}{9} \approx 0.222.[2] To convert 0.5 to balanced ternary, multiply by 3: 1.5 (digit 1, fraction 0.5); repeat: 1.5 (digit 1, fraction 0.5); yielding the repeating $0.\overline{1}.[2]From Unbalanced Ternary
Unbalanced ternary, the standard base-3 system, uses digits 0, 1, and 2 to represent non-negative integers. Balanced ternary, by contrast, employs the symmetric digit set −1, 0, and 1 (commonly denoted as T, 0, and 1), enabling representation of both positive and negative integers without a separate sign bit.[2] Conversion from unbalanced to balanced ternary proceeds via a digit-by-digit algorithm starting from the least significant trit (LSB), replacing each 2 with T (−1) while adding 1 to the next higher trit to maintain equivalence, as $2 \times 3^k = 3^{k+1} - 1 \times 3^k. This carry propagates as needed: if the higher trit reaches 3, it sets to 0 with a further carry of 1. The process continues until no more carries occur, potentially extending the number's length.[2] For instance, the unbalanced ternary number $12_3 equals 5 in decimal ($1 \times 3^1 + 2 \times 3^0 = 5). Processing from the LSB: replace the 2 with T and carry 1 to the 1, yielding 2T temporarily. The 2 then replaces with T, carrying 1 to a new position, resulting in $1TT_3. Verifying: $1 \times 3^2 + T \times 3^1 + T \times 3^0 = 9 - 3 - 1 = 5.[2] The reverse process, converting balanced ternary to unbalanced ternary, scans from the LSB as well. Each T (−1) replaces with 2, while subtracting 1 (borrowing) from the next higher trit, since -1 \times 3^k = 2 \times 3^k - 3^{k+1}. Propagation occurs if the adjusted higher trit falls below 0: a result of −2 sets the trit to 1 and propagates an additional borrow (subtract 1 further), ensuring digits stay in {0, 1, 2}.[9] Applying this to $1TT_3: the LSB T replaces with 2, borrowing 1 from the middle T, yielding −2 temporarily. Set −2 to 1 and borrow 1 from the MSB 1, resulting in 0. The final unbalanced ternary is $012_3 (leading zero omitted as $12_3), confirming $0 \times 3^2 + 1 \times 3^1 + 2 \times 3^0 = 5.General Base Conversion
Converting a number from any arbitrary integer base b (such as binary or hexadecimal) to balanced ternary typically proceeds in two steps: first, compute the equivalent decimal (base-10) value of the input number, and second, apply the standard algorithm for encoding that decimal value in balanced ternary.[15] This approach ensures accuracy for any base b \geq 2, as the decimal intermediate allows straightforward application of the balanced ternary rules.[16] The core of the second step is an iterative division algorithm adapted for balanced remainders. Starting with the decimal value N, repeatedly compute the remainder r = N \mod 3; if r = 0 or $1, record the digit as r and set N = \lfloor N / 3 \rfloor; if r = 2, record the digit as -1 (often denoted T) and set N = \lfloor N / 3 \rfloor + 1. Continue until N = 0, then read the digits from most to least significant (reversing the order of collection). This method handles both positive and negative integers directly, with negative N producing appropriate negative digits.[15] The time complexity is O(\log_3 |N|), making it efficient even for large values.[15] For bases that are powers of 3 (e.g., base 9 or 27), a direct digit-by-digit conversion is possible by expressing each source digit (ranging from 0 to $3^k - 1) as a group of k balanced trits, using a precomputed mapping table for each possible digit value to its balanced ternary equivalent.[17] However, for non-power-of-3 bases like binary (b = 2) or hexadecimal (b = 16), the decimal intermediate is standard, though grouping techniques can optimize implementation for binary inputs.[17] Consider converting the binary number 101_2 (which equals 5 in decimal) to balanced ternary. Applying the algorithm: 5 mod 3 = 2 (digit T, N = 1 + 1 = 2); 2 mod 3 = 2 (digit T, N = 0 + 1 = 1); 1 mod 3 = 1 (digit 1, N = 0). Reversing yields 1TT_3, where 1 \cdot 3^2 + (-1) \cdot 3^1 + (-1) \cdot 3^0 = 9 - 3 - 1 = 5.[15] Similarly, the hexadecimal digit A_16 (10 in decimal) converts as: 10 mod 3 = 1 (digit 1, N = 3); 3 mod 3 = 0 (digit 0, N = 1); 1 mod 3 = 1 (digit 1, N = 0). Reversing yields 101_3, where 1 \cdot 3^2 + 0 \cdot 3^1 + 1 \cdot 3^0 = 9 + 1 = 10.[15] Balanced ternary often requires fewer digits than binary to represent the same numerical values, particularly for signed integers, as the inclusion of negative digit values enables symmetric representation without a separate sign bit.[16] For large-base inputs, the iterative division method scales well, processing the decimal value directly without needing to expand the original representation fully.[15]Arithmetic Operations
Addition and Subtraction
Addition in balanced ternary is performed digit by digit from right to left, aligning numbers by their least significant trit (LST), much like in decimal or binary arithmetic, but accounting for the digits -1 (often denoted T), 0, and 1. The sum of two digits plus any incoming carry ranges from -3 to 3. To determine the output digit and outgoing carry, the total sum s is adjusted such that the result digit d satisfies d \equiv s \pmod{3} with d \in \{-1, 0, 1\}, and the carry c is \lfloor (s + 1)/3 \rfloor or equivalently determined by rules that propagate +1 or -1 carries symmetrically.[9] The following table summarizes the possible outcomes for adding two digits a and b with incoming carry c_i \in \{-1, 0, 1\}, where s = a + b + c_i, output digit d, and outgoing carry c_o:| s | d | c_o |
|---|---|---|
| -3 | 0 | -1 |
| -2 | 1 | -1 |
| -1 | -1 | 0 |
| 0 | 0 | 0 |
| 1 | 1 | 0 |
| 2 | -1 | 1 |
| 3 | 0 | 1 |
- Units column: T + 1 = -1 + 1 = 0, c_o = 0
- Threes column: 1 + 0 + 0 = 1, c_o = 0
Result: $10 (value 3).
- Units column: 1 + 1 = 2 → d = T, c_o = 1
- Threes column: 0 + 0 + 1 = 1, c_o = 0
Result: $1T (value $3 - 1 = 2).
- Units: 0 + T = -1 → d = T, c_o = 0
- Threes: T + 1 + 0 = 0 → d = 0, c_o = 0
- Nines: 1 + 0 + 0 = 1 → d = 1, c_o = 0
Result: $10T (value $9 - 1 = 8).[9]
- Units: 1 + 1 = 2 → d = T, c_o = 1
- Threes: 1 + T + 1 = 1 - 1 + 1 = 1 → d = 1, c_o = 0
Result: $1T (value 2).[2][9]