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^[1] and also in some solutions of balance puzzles.^[2]

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: "1".^[1]

Balanced ternary makes an early appearance in Michael Stifel's book Arithmetica Integra (1544).^[3] 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.^[2]

Definition[]

Let ${\displaystyle {\mathcal {D}}_{3}}$ denote the set of symbols (also called glyphs or characters) ${\displaystyle {\mathcal {D}}_{3}=\lbrace \operatorname {T} ,0,1\rbrace }$, where the symbol ${\displaystyle {\bar {1}}}$ is sometimes used in place of ${\displaystyle \operatorname {T} .}$ Define an integer-valued function ${\displaystyle f=f_{{\mathcal {D}}_{3}}:{\mathcal {D}}_{3}\to \mathbb {Z} }$ by

${\displaystyle f_{}(\operatorname {T} )=-1,}$

${\displaystyle f_{}(0)=0,}$^{[note 1]} and

${\displaystyle f_{}(1)=1}$

where the right hand sides are integers with their usual (decimal) values. This function, ${\displaystyle f_{},}$ is what rigorously and formally establishes how integer values are assigned to the symbols/glyphs in ${\displaystyle {\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 ${\displaystyle {\mathcal {D}}_{3}}$ together with the function ${\displaystyle 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 ${\displaystyle {\mathcal {D}}_{3}^{+}}$ be the Kleene plus of ${\displaystyle {\mathcal {D}}_{3}}$, which is the set of all finite length concatenated strings ${\displaystyle d_{n}\ldots d_{0}}$ of one or more symbols (called its digits) where ${\displaystyle n}$ is a non-negative integer and all ${\displaystyle n+1}$ digits ${\displaystyle d_{n},\ldots ,d_{0}}$ are taken from ${\displaystyle {\mathcal {D}}_{3}=\lbrace \operatorname {T} ,0,1\rbrace .}$ The start of ${\displaystyle d_{n}\ldots d_{0}}$ is the symbol ${\displaystyle d_{0}}$ (at the right), its end is ${\displaystyle d_{n}}$ (at the left), and its length is ${\displaystyle n+1}$. The ternary evaluation is the function ${\displaystyle v=v_{3}~:~{\mathcal {D}}_{3}^{+}\to \mathbb {Z} }$ defined by assigning to every string ${\displaystyle d_{n}\ldots d_{0}\in {\mathcal {D}}_{3}^{+}}$ the integer

${\displaystyle v\left(d_{n}\ldots d_{0}\right)~=~\sum _{i=0}^{n}f_{}\left(d_{i}\right)3^{i}.}$

The string ${\displaystyle d_{n}\ldots d_{0}}$ represents (with respect to ${\displaystyle v}$) the integer ${\displaystyle v\left(d_{n}\ldots d_{0}\right).}$ The value ${\displaystyle v\left(d_{n}\ldots d_{0}\right)}$ may alternatively be denoted by ${\displaystyle {d_{n}\ldots d_{0}}_{\operatorname {bal} 3}.}$ The map ${\displaystyle v:{\mathcal {D}}_{3}^{+}\to \mathbb {Z} }$ is surjective but not injective since, for example, ${\displaystyle 0=v(0)=v(00)=v(000)=\cdots .}$ However, every integer has exactly one representation under ${\displaystyle v}$ that does not end (on the left) with the symbol ${\displaystyle 0,}$ i.e. ${\displaystyle d_{n}=0.}$

If ${\displaystyle d_{n}\ldots d_{0}\in {\mathcal {D}}_{3}^{+}}$ and ${\displaystyle n>0}$ then ${\displaystyle v}$ satisfies:

${\displaystyle 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 ${\displaystyle v}$ satisfies a sort of recurrence relation. This recurrence relation has the initial condition ${\displaystyle v\left(\varepsilon \right)=0}$ where ${\displaystyle \varepsilon }$ is the empty string.

This implies that for every string ${\displaystyle d_{n}\ldots d_{0}\in {\mathcal {D}}_{3}^{+},}$

${\displaystyle v\left(0d_{n}\ldots d_{0}\right)=v\left(d_{n}\ldots d_{0}\right)}$

which in words says that leading ${\displaystyle 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 ${\displaystyle v}$ can be computed, where (as before) all integer are written in decimal (base 10) and all elements of ${\displaystyle {\mathcal {D}}_{3}^{+}}$ are just symbols.

${\displaystyle {\begin{alignedat}{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(11\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(10\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{alignedat}}}$

and using the above recurrence relation

${\displaystyle v\left(101\operatorname {T} \right)=f_{}\left(1\right)3^{3}+v\left(01\operatorname {T} \right)=(1)27+v\left(1\operatorname {T} \right)=27+2=29.}$

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,

10_bal3 = 1 × 3¹ + 0 × 3⁰ = 3₁₀

10