Balanced ternary: Difference between revisions

Revision as of 04:33, 13 July 2019

Latest revision as of 06:42, 29 August 2025

(140 intermediate revisions by 49 users not shown)

Line 1:

{{Short description|Numeral system using the values -1, 0 and 1}}

{{numeral systems}}

'''Balanced ternary''' is a [[Non-standard positional numeral systems|non-standard positionalternary numeral system]] (ai.e. base 3 with three [[Signed-digitNumerical representationdigit|balanced formdigits]]), usedthat inuses somea early computers<ref name=setun/> and useful in the solution ofbalanced [[balancesigned-digit puzzlerepresentation]]s.<ref name=hayes/>of It is athe [[Ternary numeral system|ternaryinteger]] (base&nbsp;3) number systems in which the digits have the values –1[[−1]], [[0]], and [[1,]]. This stands in contrast to the standard (unbalanced) ternary system, in which digits have values 0, 1 and 2.

BalancedThe 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. WhileThe binarybalanced numeralsternary withsystem digitsis 0an andexample 1of providea the simplest[[Non-standard positional numeral systemsystems|non-standard forpositional [[naturalnumeral numberssystem]]. (orIt forwas positiveused integersin ifsome usingearly computers<ref 1name=setun/> and 2has asalso thebeen digits),used balancedto ternary provides the simplest self-contained positional numeral system forsolve [[integersbalance puzzle]]s.<ref name=hayes/>

Different sources use different glyphs used to represent the three digits in balanced ternary. In this article, T (which resembles a [[typographical ligature|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 alphabet|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: "{{turned<span one}}class="plainlinks"></span><span style="display:inline-block;vertical-align:-0.05em;transform:matrix(-1, 0, 0, -1, 0, 0);">1</span>".<ref name=setun>{{cite book|title=Programming|year=1963|___location=Moscow|author=N. A. Krinitsky |author2=G. A. Mironov |author3=G. D. Frolov|editor=M. R. Shura-Bura|language=ru|chapter=Chapter 10. Program-controlled machine Setun}}</ref>

Balanced ternary makes an early appearance in [[Michael Stifel]]'s book ''Arithmetica Integra'' (1544).<ref>{{citation

Line 11 ⟶ 12:

| title = Arithmetica integra

| url = https://archive.org/stream/bub_gb_ywkW9hDd7IIC#page/n85/mode/2up

| year = 1544| publisher = apud Iohan Petreium }}.</ref> 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 (physicist)|John Leslie]], [[Augustin-Louis Cauchy]], and possibly even the ancient Indian [[Vedas]].<ref name=hayes>{{citation | first=Brian|last=Hayes|authorlink=Brian Hayes (scientist)|title=Third base|journal=American Scientist|url=http://bit-player.org/bph-publications/AmSci-2001-11-Hayes-ternary.pdf|year=2001|volume=89|issue=6|pages=490&ndash;494|doi=10.1511/2001.40.3268}}. Reprinted in {{citation|title=Group Theory in the Bedroom, and Other Mathematical Diversions|first=Brian|last=Hayes|authorlink=Brian Hayes (scientist)|publisher=Farrar, Straus and Giroux|year=2008|isbn=9781429938570|pages=179–200|url=https://books.google.com/books?id=1ZkYEFi3DMMC&pg=PA179}}</ref>

==In computerDefinition design==

{{See also|Signed-digit representation}}

Let <math>\mathcal{D}_{3} := \lbrace \operatorname{T}, 0, 1 \rbrace</math> denote the set of [[Symbol (mathematics)|symbols]] (also called ''glyphs'' or ''characters''), where the symbol <math>\bar{1}</math> is sometimes used in place of <math>\operatorname{T}.</math>

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. The one-digit [[multiplication table]] has no carries in balanced ternary, and the addition table has only two symmetric carries instead of three.

Define an [[integer]]-valued function <math>f = f_{\mathcal{D}_{3}} : \mathcal{D}_{3} \to \mathbb{Z}</math> by

:<math>\begin{align}

Because balanced ternary provides a uniform self-contained representation for integers, the distinction between signed and unsigned numerals no longer needs to be made; thereby eliminating the need to duplicate operator sets into signed and unsigned varieties, as most CPU architectures and many programming languages currently do.

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

f_{}(0) &= 0, \\

f_{}(1) &= 1,

\end{align}</math><ref>The symbols <math>0</math> and <math>1</math> appear twice in the equalities <math>f_{}(0) = 0</math> and <math>f_{}(1) = 1,</math> but these instances do not represent the same thing. The right hand side <math>0</math> and <math>1</math> mean the integers <math>\in\Z,</math> but the instances inside <math>f</math>'s parentheses (which belong to <math>\mathcal{D}_{3}</math>) should be thought of as being nothing more than symbols.</ref>

where the right hand sides are integers with their usual values. This function, <math>f_{},</math> is what rigorously and formally establishes how integer values are assigned to the symbols/glyphs in <math>\mathcal{D}_{3}.</math> 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 <math>\mathcal{D}_{3}</math> together with the function <math>f_{}</math> forms a balanced [[signed-digit representation]] called the ''balanced ternary'' system.

==Conversion to decimal==

It can be used to represent integers and real numbers.

=== Ternary integer evaluation ===

Let <math>\mathcal{D}_{3}^{+}</math> be the [[Kleene plus]] of <math>\mathcal{D}_{3}</math>, which is the set of all finite length [[concatenation|concatenated]] [[String (computer science)|strings]] <math>d_n \ldots d_0</math> of one or more symbols (called its ''digits'') where <math>n</math> is a non-negative integer and all <math>n + 1</math> digits <math>d_n, \ldots, d_0</math> are taken from <math>\mathcal{D}_{3} = \lbrace \operatorname{T}, 0, 1 \rbrace.</math> The ''start'' of <math>d_n \ldots d_0</math> is the symbol <math>d_0</math> (at the right), its ''end'' is <math>d_n</math> (at the left), and its ''length'' is <math>n + 1</math>. The ''ternary evaluation'' is the function <math>v = v_{3} ~:~ \mathcal{D}_{3}^{+} \to \mathbb{Z}</math> defined by assigning to every string <math>d_n \ldots d_0 \in \mathcal{D}_{3}^{+}</math> the integer

:<math>v\left( d_n \ldots d_0 \right) ~=~ \sum_{i=0}^{n} f_{} \left( d_{i} \right) 3^{i}.</math>

The string <math>d_n \ldots d_0</math> ''represents'' (with respect to <math>v</math>) the integer <math>v\left( d_n \ldots d_0 \right).</math> The value <math>v\left( d_n \ldots d_0 \right)</math> may alternatively be denoted by <math>{d_n \ldots d_0}_{\operatorname{bal}3}.</math>

The map <math>v : \mathcal{D}_{3}^{+} \to \mathbb{Z}</math> is [[Surjective map|surjective]] but not injective since, for example, <math>0 = v(0) = v(00) = v(0 0 0) = \cdots.</math> However, every nonzero integer has exactly one representation under <math>v</math> that does not ''end'' (on the left) with the symbol <math>0,</math> i.e. <math>d_n = 0 .</math>

If <math>d_n \ldots d_0 \in \mathcal{D}_{3}^{+}</math> and <math>n > 0</math> then <math>v</math> satisfies:

:<math>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)</math>

which shows that <math>v</math> satisfies a sort of [[recurrence relation]]. This recurrence relation has the initial condition

<math>v\left( \varepsilon \right) = 0</math>

where <math>\varepsilon</math> is the empty string.

This implies that for every string <math>d_n \ldots d_0 \in \mathcal{D}_{3}^{+},</math>

:<math>v\left( 0 d_n \ldots d_0 \right) = v\left( d_n \ldots d_0 \right)</math>

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

:<math>\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}

</math>

and using the above recurrence relation

:<math>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.</math>

== 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 3^''n''. 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×31 × 3¹ + 0×30 × 3⁰ = 3_10dec

: 10T10𝖳_bal3 = 1×31 × 3² + 0×30 × 3¹ + (−1)×3 × 3⁰ = 8_10dec

: −9_10dec = −1×3−1 × 3² + 0×30 × 3¹ + 0×30 × 3⁰ = T00𝖳00_bal3

: 8_10dec = 1×31 × 3² + 0×30 × 3¹ + (−1)×3 × 3⁰ = 10T10𝖳_bal3

Similarly, the first place to the right of the radix point holds 3⁻¹ = {{sfrac|1|3}}, the second place holds 3⁻² = {{sfrac|1|9}}, and so on. For instance,

: −{{sfrac|2|3}}_10dec = −1 + {{sfrac|1|3}} = −1×3−1 × 3⁰ + 1×31 × 3⁻¹ = T𝖳.1_bal3.

<div style="display: flex; column-gap: 1em; margin-inline-start: 1.5em;">

:{| class="wikitable" style="border: none; text-align:right"

{| class="wikitable" style="border: none; text-align:right"

! Dec !! Bal3 !! Expansion !!!! Dec !! Bal3 !! Expansion

! Dec !! Bal3 !! Expansion

|-

| 0 || 0 || 0 |||| || ||

|-

| 1 || 1 || +1 |||| −1 || T || −1

|-

| 2 || 1T1𝖳 || +3−1 |||| −2 || T1 || −3+1

|-

| 3 || 10 || +3 |||| −3 || T0 || −3

|-

| 4 || 11 || +3+1 |||| −4 || TT || −3−1

|-

| 5 || 1TT1𝖳𝖳 || +9−3−1 |||| −5 || T11 || −9+3+1

|-

| 6 || 1T01𝖳0 || +9−3 |||| −6 || T10 || −9+3

|-

| 7 || 1T11𝖳1 || +9−3+1 |||| −7 || T1T || −9+3−1

|-

| 8 || 10T10𝖳 || +9−1 |||| −8 || T01 || −9+1

|-

| 9 || 100 || +9 |||| −9 || T00 || −9

|-

| 10 || 101 || +9+1 |||| −10 || T0T || −9−1

|-

| 11 || 11T11𝖳 || +9+3−1 |||| −11 || TT1 || −9−3+1

|-

| 12 || 110 || +9+3 |||| −12 || TT0 || −9−3

|-

| 13 || 111 || +9+3+1 |||| −13 || TTT || −9−3−1

|}

{| class="wikitable" style="border: none; text-align:right"

! Dec !! Bal3 !! Expansion

|-

| 0 || 0 || 0

|-

| −1 || 𝖳 || −1

|-

| −2 || 𝖳1 || −3+1

|-

| −3 || 𝖳0 || −3

|-

| −4 || 𝖳𝖳 || −3−1

|-

| −5 || 𝖳11 || −9+3+1

|-

| −6 || 𝖳10 || −9+3

|-

| −7 || 𝖳1𝖳 || −9+3−1

|-

| −8 || 𝖳01 || −9+1

|-

| −9 || 𝖳00 || −9

|-

| −10 || 𝖳0𝖳 || −9−1

|-

| −11 || 𝖳𝖳1 || −9−3+1

|-

| −12 || 𝖳𝖳0 || −9−3

|-

| −13 || 𝖳𝖳𝖳 || −9−3−1

|}

</div>

An integer is divisible by three if and only if the digit in the units place is zero.

We may check the [[Parity (mathematics)|parity]] of a balanced ternary integer by checking the parity of the sum of all [[trit (computing)|trit]]strits. 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]].<ref>{{cite web |url=http://www.abhijit.info/tristate/tristate.html |title=Balanced ternary |last=Bhattacharjee |first=Abhijit |date=24 July 2006 |archiveurl=https://web.archive.org/web/20090919053547/http://www.abhijit.info/tristate/tristate.html |archivedate=2009-09-19}}</ref>

:{| class="wikitable"

|-

|-align="center"

! Decimal

! Decimal !! −0.9 !! −0.8 !! −0.7 !! −0.6 !! −0.5 !! −0.4 !! −0.3 !! −0.2 !! −0.1 !! 0

! style="text-align: right" | −0.9

|-align="center"

! style="text-align: right" | −0.8

! style="text-align: right" | −0.7

! style="text-align: right" | −0.6

! style="text-align: right" | −0.5

! style="text-align: right" | −0.4

! style="text-align: right" | −0.3

! style="text-align: right" | −0.2

! style="text-align: right" | −0.1

! style="text-align: right" | 0

|-

! Balanced Ternary

| T𝖳.{{overline|010T010𝖳}}||T𝖳.{{overline|1TT11𝖳𝖳1}}|| T𝖳.{{overline|10T010𝖳0}}|| T𝖳.{{overline|11TT11𝖳𝖳}}|| 0.{{overline|T𝖳}} or T𝖳.{{overline|1}} || 0.{{overline|TT11𝖳𝖳11}} || 0.{{overline|T010𝖳010}} || 0.{{overline|T11T𝖳11𝖳}} || 0.{{overline|0T010𝖳01}} || 0

|-

|-align="right"

! Decimal

! Decimal !! 0.9 !! 0.8 !! 0.7 !! 0.6 !! 0.5 !! 0.4 !! 0.3 !! 0.2 !! 0.1 !! 0

|! style="text-align="center: right" | 0.9

! style="text-align: right" | 0.8

! style="text-align: right" | 0.7

! style="text-align: right" | 0.6

! style="text-align: right" | 0.5

! style="text-align: right" | 0.4

! style="text-align: right" | 0.3

! style="text-align: right" | 0.2

! style="text-align: right" | 0.1

! style="text-align: right" | 0

|-

! Balanced Ternary

| 1.{{overline|0T010𝖳01}}||1.{{overline|T11T𝖳11𝖳}}|| 1.{{overline|T010𝖳010}}|| 1.{{overline|TT11𝖳𝖳11}}|| 0.{{overline|1}} or 1.{{overline|T𝖳}} || 0.{{overline|11TT11𝖳𝖳}} || 0.{{overline|10T010𝖳0}} || 0.{{overline|1TT11𝖳𝖳1}} || 0.{{overline|010T010𝖳}} || 0

|}

In decimal or binary, integer values and terminating fractions have multiple representations. For example, {{sfrac|1|10}} = 0.1 = 0.1{{overline|0}} = 0.0{{overline|9}}. And, {{sfrac|1|2}} = 0.1₂ = 0.1{{overline|0}}₂ = 0.0{{overline|1}}₂. Some balanced ternary fractions have multiple representations too. For example, {{sfrac|1|6}} = 0.1{{overline|T𝖳}}_bal3 = 0.0{{overline|1}}_bal3. 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−1s after the radix point in order to gain a representations of integer or terminating fraction.

[[Donald Knuth]]<ref name="Knuth">{{Cite book

[[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 {{sfrac|1|2}} is not exceptional; it has two equally valid representations, and two equally valid truncations: 0.{{overline|1}} (round to 0, and truncate to 0) and 1.{{overline|T}} (round to 1, and truncate to 1).

|last=Knuth

|first=Donald

|authorlink=Donald Knuth

|title=The art of Computer Programming

|volume=2

|pages=195–213

|publisher=Addison-Wesley

|year=1997

|isbn=0-201-89684-2}}</ref> has pointed out that truncation and rounding are the same operation in balanced ternary&mdash;they produce exactly the same result (a property shared with other balanced numeral systems). The number {{sfrac|1|2}} is not exceptional; it has two equally valid representations, and two equally valid truncations: 0.{{overline|1}} (round to 0, and truncate to 0) and 1.{{overline|𝖳}} (round to 1, and truncate to 1). With an odd [[radix]], [[Rounding#Double rounding|double rounding]] is also equivalent to directly rounding to the final precision, unlike with an even radix.

The basic operations&mdash;addition, subtraction, multiplication, and division&mdash;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.

Line 88 ⟶ 225:

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===

<div style="display: flex; column-gap: 1em; margin-inline-start: 1.5em;">

:{| class="wikitable"

{| class="wikitable" style="text-align: center;"

!Fraction!!colspan="2"|Balanced ternary!! !!Fraction!!colspan="2"|Balanced ternary

!Fraction!!colspan="2"|Balanced ternary

|- align="center"

|-

|1||colspan="2"|1|| ||{{sfrac|1|11}}||colspan="2"|0.{{overline|01T11}}

|1||colspan="2"|1

|- align="center"

|-

|{{sfrac|1|2}}||0.{{overline|1}}||1.{{overline|T}}|| ||{{sfrac|1|12}}||colspan="2"|0.0{{overline|1T}}

|{{sfrac|1|2}}||0.{{overline|1}}||1.{{overline|𝖳}}

|- align="center"

|-

|{{sfrac|1|3}}||colspan="2"|0.1|| ||{{sfrac|1|13}}||colspan="2"|0.{{overline|01T}}

|{{sfrac|1|3}}||colspan="2"|0.1

|- align="center"

|-

|{{sfrac|1|4}}||colspan="2"|0.{{overline|1T}}|| ||{{sfrac|1|14}}||colspan="2"|0.{{overline|01T0T1}}

|{{sfrac|1|4}}||colspan="2"|0.{{overline|1𝖳}}

|- align="center"

|-

|{{sfrac|1|5}}||colspan="2"|0.{{overline|1TT1}}|| ||{{sfrac|1|15}}||colspan="2"|0.0{{overline|1TT1}}

|{{sfrac|1|5}}||colspan="2"|0.{{overline|1𝖳𝖳1}}

|- align="center"

|-

|{{sfrac|1|6}}||0.0{{overline|1}}||0.1{{overline|T}}|| ||{{sfrac|1|16}}||colspan="2"|0.{{overline|01TT}}

|{{sfrac|1|6}}||0.0{{overline|1}}||0.1{{overline|𝖳}}

|- align="center"

|-

|{{sfrac|1|7}}||colspan="2"|0.{{overline|0110TT}}|| ||{{sfrac|1|17}}||colspan="2"|0.{{overline|01TTT10T0T111T01}}

|{{sfrac|1|7}}||colspan="2"|0.{{overline|0110𝖳𝖳}}

|- align="center"

|-

|{{sfrac|1|8}}||colspan="2"|0.{{overline|01}}|| ||{{sfrac|1|18}}||0.00{{overline|1}}||0.01{{overline|T}}

|{{sfrac|1|8}}||colspan="2"|0.{{overline|01}}

|- align="center"

|-

|{{sfrac|1|9}}||colspan="2"|0.01|| ||{{sfrac|1|19}}||colspan="2"|0.{{overline|00111T10100TTT1T0T}}

|{{sfrac|1|9}}||colspan="2"|0.01

|- align="center"

|-

|{{sfrac|1|10}}||colspan="2"|0.{{overline|010T}}|| ||{{sfrac|1|20}}||colspan="2"|0.{{overline|0011}}

|{{sfrac|1|10}}||colspan="2"|0.{{overline|010𝖳}}

|}

{| class="wikitable" style="text-align: center;"

!Fraction!!colspan="2"|Balanced ternary

|-

|{{sfrac|1|11}}||colspan="2"|0.{{overline|01𝖳11}}

|-

|{{sfrac|1|12}}||colspan="2"|0.0{{overline|1𝖳}}

|-

|{{sfrac|1|13}}||colspan="2"|0.{{overline|01𝖳}}

|-

|{{sfrac|1|14}}||colspan="2"|0.{{overline|01𝖳0𝖳1}}

|-

|{{sfrac|1|15}}||colspan="2"|0.0{{overline|1𝖳𝖳1}}

|-

|{{sfrac|1|16}}||colspan="2"|0.{{overline|01𝖳𝖳}}

|-

|{{sfrac|1|17}}||colspan="2"|0.{{overline|01𝖳𝖳𝖳10𝖳0𝖳111𝖳01}}

|-

|{{sfrac|1|18}}||0.00{{overline|1}}||0.01{{overline|𝖳}}

|-

|{{sfrac|1|19}}||colspan="2"|0.{{overline|00111𝖳10100𝖳𝖳𝖳1𝖳0𝖳}}

|-

|{{sfrac|1|20}}||colspan="2"|0.{{overline|0011}}

|}

</div>

The conversion of a repeating balanced ternary number to a fraction is analogous to [[Repeating decimal#Converting repeating decimals to fractions|converting a repeating decimal]]. For example (because of 111111_bal3 = ({{sfrac|3⁶ − 1|3 − 1}})_10dec):

: <math> 0.1\overline{\mathrm{110TT0} } =\tfrac{\mathrm{1110TT0-1} }{\mathrm{111111\times 1T\times 10}}=\tfrac{\mathrm{1110TTT} } {\mathrm{111111\times 1T0}} =\tfrac{\mathrm{111\times 1000T} } {\mathrm{111\times 1001\times 1T0}} =\tfrac{\mathrm{1111\times 1T}}{\mathrm{1001\times 1T0}} =\tfrac{1111}{10010}=\tfrac{\mathrm{1T1T}}{\mathrm{1TTT0}} =\tfrac{101}{\mathrm{1T10} } </math>

=== Conversion from unbalanced ternary ===

==Irrational numbers==

As in any other integer base, algebraic irrationals and transcendental numbers do not terminate or repeat. For example:

:<math>\begin{array}{r|l}

\text{Decimal} & \text{Balanced ternary} \\

\hline

\sqrt{2}=1.4142135623731... & \sqrt{\mathrm{1T}}=\mathrm{1.11T1TT00T00T01T0T00T00T01TT...} \\

\sqrt{3}=1.7320508075689... & \sqrt{\mathrm{10}}=\mathrm{1T.T1TT10T0000TT1100T0TTT011T0...} \\

\sqrt{5}=2.2360679774998... & \sqrt{\mathrm{1TT}}=\mathrm{1T.1T0101010TTT1TT11010TTT01T1...} \\

\phi=\frac{1 + \sqrt{5}}{2}=1.6180339887499... & \phi=\frac{1 + \sqrt{\mathrm{1TT}}}{\mathrm{1T}}=\mathrm{1T.T0TT01TT0T10TT11T0011T10011...} \\

\tau=6.28318530717959... & \tau=\mathrm{1T0.10TT0T1100T110TT0T1TT000001}...\\

\pi=3.14159265358979... & \pi=\mathrm{10.011T111T000T011T1101T111111}... \\

e=2.71828182845905... & e=\mathrm{10.T0111TT0T0T111T0111T000T11T}...

\end{array}</math>

==Complex numbers==

{{Empty section|date=July 2019}}

== Conversion from ternary ==

Unbalanced ternary can be converted to balanced ternary notation in two ways:

*Add 1 trit-by-trit from the first non-zero trit with carry, and then subtract 1 trit-by-trit from the same trit without borrow. For example,

*: 021₃ + 11₃ = 102₃, 102₃ − 11₃ = 1T1_bal3 = 7_10dec.

*If a 2 is present in ternary, turn it into 1T. For example,

*: 0212₃ = 0010_bal3 + 1T00_bal3 + 001T_bal3 = 10TT_bal3 = 23_10dec

:{| class="wikitable floatright" style="{{float right}} text-align: center"

|-

! Balanced || Logic || Unsigned

Line 157 ⟶ 302:

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 {{nowrap|''x'' + ''y'' − ''b''}} when computed using conventional unsigned ternary arithmetic. Similarly, if ''x'' and ''y'' are conventional unsigned ternary numbers, their sum is {{nowrap|''x'' + ''y'' + ''b''}} when computed using balanced ternary arithmetic.

===Conversion to balanced ternary from any integer base to balanced ternary===

We may convert to balanced ternary with the following formula:

Line 171 ⟶ 316:

For instance,

−25.4_10dec = −(1T×101¹ + 1TT×101⁰ + 11×101⁻¹)

= −(1T×101¹ + 1TT1TT×101⁰ + 11÷10111×101^T)

= −(1T×101 + 1TT + 11×0.{{overline|010T}})

= −(1T1T + 1TT + 0.{{overline|11TT}})

= −10T1.{{overline|11TT}}

= T01T.{{overline|TT11}}

1010.1₂ = 1T¹⁰ + 1T¹ + 1T⁻¹

= 10T1T¹⁰ + 1T¹ + 0.{{overline|1}}1T^T

= 101.{{overline|1}}

= 10T + 1T + 0.{{overline|1}}

= 101.{{overline|1}}

== Addition, subtraction and multiplication and division ==

Line 257 ⟶ 411:

______________ ______________ _______________

1T0T10.0TT1 1T1001.TTT1 1T1001.TTT1

+ 1T + T T T1 + T TT1

______________ ________________ ________________

1T1110.0TT1 1110TT.TTT1 1110TT.TTT1

Line 266 ⟶ 420:

===Multi-trit multiplication===

Multi-trit multiplication is analogous to that inof decimalbinary and binarydecimal.

1TT1.TT

Line 280 ⟶ 434:

===Multi-trit division===

Balanced ternary division is analogous to decimalthat orof binary divisionand decimal.

However, 0.5_10dec = 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

Line 322 ⟶ 476:

0

Another example,

101.TTTTTTTTT…TTTTTTTTT...

or 100.111111111…111111111...

0.5 × divisor 1T _________________

divisor 11 )111T 11 > 1T, set 1

Line 330 ⟶ 484:

1 T1 < 1 < 1T, set 0

___

1T 1T = 1T, trits end, set 1.TTTTTTTTT…TTTTTTTTT... or 0.111111111…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 [https://dfns.dyalog.com/n_bt.htm 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==

Line 375 ⟶ 546:

...

Extraction of the cube root in balanced ternary is similarly analogous to extraction in decimal or binary:

:<math>(10\cdot x+y)^{10}-1000\cdot x^{10}=y^{10}+1000\cdot x^{\mathrm{1T}}\cdot y+ 100\cdot x\cdot y^{\mathrm{1T}}+y^{10}=

\begin{cases}

\mathrm{T}+\mathrm{T000}\cdot x^{\mathrm{1T}}+100\cdot x+\mathrm{T}, & y=\mathrm{T}\\

0, & y=0\\

1+1000\cdot x^{\mathrm{1T}}+100\cdot x+1, & y=1

\end{cases}

Line 387 ⟶ 558:

1. 1 T 1 0 ...

_____________________

³√¹⁰√ 1T

− 1 1<1T<10T,set 1

_______

Line 416 ⟶ 587:

1T10T000000

...

Hence {{radic|2|3}}_dec = {{radic|1T|10}}_bal3 = 1.259921_10dec = 1.1T1&nbsp;000&nbsp;111&nbsp;001&nbsp;T01&nbsp;00T&nbsp;1T1&nbsp;T10&nbsp;111_bal3.

==Irrational numbers==

==Other applications==

As in any other integer base, algebraic irrationals and transcendental numbers do not terminate or repeat. For example:

Balanced ternary has other applications besides computing. For example, a classical two-pan [[Weighing scale#Balance|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_bal3) 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.

:{| class="wikitable"

!Decimal !! Balanced ternary

|-

|<math>\sqrt{2}=1.4142135623731\ldots</math> || <math>\sqrt{\mathrm{1T}}=\mathrm{1.11T1TT00T00T01T0T00T00T01TT\ldots}</math>

|-

|<math>\sqrt{3}=1.7320508075689\ldots</math> || <math>\sqrt{\mathrm{10}}=\mathrm{1T.T1TT10T0000TT1100T0TTT011T0\ldots}</math>

|-

|<math>\sqrt{5}=2.2360679774998\ldots</math> || <math>\sqrt{\mathrm{1TT}}=\mathrm{1T.1T0101010TTT1TT11010TTT01T1\ldots}</math>

|-

|<math display="inline">\varphi=\frac{1 + \sqrt{5}}{2}=1.6180339887499\ldots</math> || <math display="inline">\varphi=\frac{1 + \sqrt{\mathrm{1TT}}}{\mathrm{1T}}=\mathrm{1T.T0TT01TT0T10TT11T0011T10011\ldots}</math>

|-

|<math>\tau=6.28318530717959\ldots</math> || <math>\tau=\mathrm{1T0.10TT0T1100T110TT0T1TT000001}\ldots</math>

|-

|<math>\pi=3.14159265358979\ldots</math> || <math>\pi=\mathrm{10.011T111T000T011T1101T111111}\ldots</math>

|-

|<math>e=2.71828182845905\ldots</math> || <math>e=\mathrm{10.T0111TT0T0T111T0111T000T11T}\ldots</math>

|}

The balanced ternary expansions of <math>\pi</math> is given in [[OEIS]] as {{OEIS link|A331313}}, that of <math>e</math> in {{OEIS link|A331990}}.

== Applications ==

=== In computer design ===

[[File:Balanced ternary operation tables.svg|thumb|Operation tables]]<!--Maybe that "al TRIT più alto" table deserves some explanation.-->

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,"<ref name="Knuth"/> noting that,

{{quote|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 <math>\log_3 2 \approx 63 \%</math> as many digit positions for its representation."<ref name="Knuth"/>}}

More recently, balanced ternary numbers have been proposed for some highly-efficient low-resolution implementations of [[artificial neural networks]]. In [[deep learning]], neural nets usually use continuous (floating-point) values, but there are many works investigating quantisation and binarisation to create neural nets that can run with much lower power and/or lower memory requirements. Balanced ternary numbers are proposed to be used for the network parameters, because they are extremely compact, but can naturally represent excitatory/inhibitory/null activation patterns.<ref>{{cite arXiv

| last = Li

| first = Fengfu

| title = Ternary Weight Networks

|date = 2022

| class = cs.CV

| eprint = 1605.04711

}}</ref><ref>{{cite arXiv

| last = Ma

| first = Shuming

| title = The era of 1-bit LLMs: All large language models are in 1.58 bits

| date = 2024

| class = cs.CL

| eprint = 2402.17764

}}</ref>

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]]<ref>{{cite journal

| last = Andrews | first = George E.

| doi = 10.1090/S0273-0979-07-01180-9

| issue = 4

| journal = Bulletin of the American Mathematical Society

| mr = 2338365

| pages = 561–573

| series = New Series

| title = Euler's "De Partitio numerorum"

| volume = 44

| year = 2007| doi-access = free

}}</ref>

:<math>\prod_{n=0}^{\infty} \left(x^{-3^n}+1+x^{3^n}\right)=\sum_{n=-\infty}^{\infty}x^n.</math>

Balanced ternary has other applications besides computing. For example, a classical two-pan [[Weighing scale#Balance|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_dec = 1T1T0_bal3) 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_bal3), the buyer pays 1¤ + 9¤ and receives 3¤ in change.

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_dec = 1T1_bal3), the buyer pays 1¤ + 9¤ and receives 3¤ in change.

They may also provide a more natural representation for the [[Qutrit]] and systems that make use of it.

==See also==

* [[Setun]], a [[ternary computer]]

* [[TernarySigned-digit logicrepresentation]]

* [[Numeral system]]

* [[Methods of computing square roots]]

* [[SalamisNumeral Tabletsystem]]

* [[Qutrit]]

* [[Salamis Tablet]]

* [[Ternary computer]]

** [[Setun]], a ternary computer

* [[Ternary logic]]

* [[Generalized balanced ternary]]

==References==

{{reflist}}

{{reflist|group=note}}

==External links==

{{commons category|Balanced ternary}}

*[http://www.computer-museum.ru/english/setun.htm Development of ternary computers at Moscow State University]

*[https://web.archive.org/web/20090312094241/http://abhijit.info/tristate/tristate.html Representation of Fractional Numbers in Balanced Ternary]

*[httphttps://www.americanscientist.org/issues/pubarticle/third-base/ "Third base"], ternary and balanced ternary number systems

*[https://web.archive.org/web/20110712221950/http://www.hostsrv.com/webmaa/app1/MSP/webm1010/ternary.msp The Balanced Ternary Number System] (includes decimal integer to balanced ternary converter)

*{{OEIS el|1=A182929|2=The binomial triangle reduced to balanced ternary lists|formalname=The rows of the binomial triangle reduced to balanced ternary lists encoded as decimal numbers}}

*[http://userpages.wittenberg.edu/bshelburne/BalancedTernaryTalkSu09.pdf Balanced (Signed) Ternary Notation] {{Webarchive|url=https://web.archive.org/web/20160303182504/http://userpages.wittenberg.edu/bshelburne/BalancedTernaryTalkSu09.pdf |date=2016-03-03 }} by Brian J. Shelburne (PDF file)

*[http://www.mortati.com/glusker/fowler/ The ternary calculating machine of Thomas Fowler] by Mark Glusker

[[de:Ternärsystem#Balanciert]]

[[Category:Computer arithmetic]]

[[Category:Non-standard positional numeral systems]]

[[Category:Ternary computers]]

[[Category:Numeral systems]]

[[de:Ternärsystem#Balanciert]]