TAOCP 4.2.1 Exercise 7
Balanced ternary uses radix $b=3$ and digits \bar 1=-1,\qquad 0,\qquad 1.
Section 4.2.1: Single-Precision Calculations
Exercise 7. [27] Discuss floating point arithmetic using balanced ternary notation.
Verified: yes
Solve time: 9m56s
Balanced ternary uses radix $b=3$ and digits
$$ \bar 1=-1,\qquad 0,\qquad 1. $$
A real number is represented in normalized floating-point form as
$$ x=\pm m,3^e, $$
where the significand (mantissa)
$$ m=.d_1d_2\cdots d_p $$
is a balanced ternary fraction with digits $d_i\in{\bar1,0,1}$, and normalization requires $d_1\neq0$. Since the leading digit must be $\pm1$, every nonzero number has a unique normalized representation.
For example,
$$ 1=.1\times 3^1, $$
and
$$ \frac13=.1\times 3^0. $$
Because the digits are symmetric about zero, negative numbers need not be represented by a separate sign bit. One may either allow a separate sign, as in ordinary floating-point systems, or simply permit the leading digit to be $\bar1$.
Range and normalization
With precision $p$, the normalized significands satisfy
$$ \frac13\le |m|<1. $$
Hence the exponent determines the scale exactly as in ordinary floating-point arithmetic. Overflow occurs when the exponent exceeds the largest permitted value; underflow occurs when it falls below the smallest permitted value.
Normalization after arithmetic is straightforward. If an operation produces a leading digit $0$, the significand is shifted left and the exponent decreased. If it produces magnitude at least $1$, the significand is shifted right and the exponent increased.
Addition and subtraction
Addition proceeds exactly as in radix-$3$ arithmetic. Exponents are first aligned:
$$ m_1 3^{e_1}+m_2 3^{e_2}. $$
Assume $e_1\ge e_2$. Then
$$ m_2 3^{e_2} = (m_2 3^{e_2-e_1})3^{e_1}, $$
so the significands may be added.
Balanced digits give particularly simple carry rules. Since the digit set is symmetric, any temporary digit $t$ can be rewritten as a balanced digit plus a carry:
$$ 2=\bar1+1\cdot3, \qquad -2=1-1\cdot3. $$
Thus carries are always $-1$, $0$, or $1$. The symmetry reduces the frequency and complexity of carry propagation compared with ordinary ternary or decimal arithmetic.
Subtraction is especially simple because
$$ -(d_1d_2\cdots d_p) = (-d_1)(-d_2)\cdots(-d_p), $$
so subtraction is performed by digitwise negation followed by addition.
Multiplication
Multiplication is also analogous to ordinary floating-point multiplication:
$$ (m_1 3^{e_1})(m_2 3^{e_2}) = (m_1m_2)3^{e_1+e_2}. $$
The significands are multiplied, the exponents added, and the result normalized. Since each digit is $-1$, $0$, or $1$, partial products are especially simple:
$$ 1\cdot d=d,\qquad 0\cdot d=0,\qquad \bar1\cdot d=-d. $$
Thus multiplication tables are smaller than in most other radices.
Rounding
Suppose only $p$ digits are retained. After an operation one obtains
$$ .d_1d_2\cdots d_p d_{p+1}\cdots . $$
The discarded tail determines the rounding. Since the digit set is symmetric, rounding to nearest is naturally unbiased. If the discarded part exceeds half a unit in the last place, one adds or subtracts one unit of the $p$-th digit according to the sign of the remainder.
The spacing between adjacent normalized $p$-digit numbers near exponent $e$ is
$$ 3^{,e-p}. $$
Hence the maximum rounding error under rounding to nearest is
$$ \frac12,3^{,e-p}, $$
exactly one-half unit in the last place.
Advantages of balanced ternary
Balanced ternary has several attractive features for floating-point arithmetic.
- Negative values are represented symmetrically.
- Subtraction is reduced to digitwise negation and addition.
- Carries are balanced and tend to propagate less severely.
- Multiplication uses only the coefficients $-1$, $0$, and $1$.
The overall floating-point structure is the same as for any radix-$b$ system, but the symmetric digit set of balanced ternary leads to particularly elegant rules for representation, carrying, subtraction, and rounding.