SUPPORT THE WORK

GetWiki

balanced ternary

ARTICLE SUBJECTS
aesthetics  →
being  →
complexity  →
database  →
enterprise  →
ethics  →
fiction  →
history  →
internet  →
knowledge  →
language  →
licensing  →
linux  →
logic  →
method  →
news  →
perception  →
philosophy  →
policy  →
purpose  →
religion  →
science  →
sociology  →
software  →
truth  →
unix  →
wiki  →
ARTICLE TYPES
essay  →
feed  →
help  →
system  →
wiki  →
ARTICLE ORIGINS
critical  →
discussion  →
forked  →
imported  →
original  →
balanced ternary
[ temporary import ]
please note:
- the content below is remote from Wikipedia
- it has been imported raw for GetWiki
{{Short description|Numeral system that uses the digits -1, 0 and, 1}}{{numeral systems}}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 has also been used to solve balance puzzles.Different sources use different glyphs 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".BOOK, Programming, 1963, Moscow, N.A.Krinitsky, G.A.Mironov, G.D.Frolov, M.R.Shura-Bura, ru, Chapter 10. Program-controlled machine Setun, Balanced ternary makes an early appearance in Michael Stifel's book Arithmetica Integra (1544).{{citation
| last = Stifel | first = Michael | author-link = Michael Stifel
| language = Latin
| page = 38
| title = Arithmetica integra
| url =weblink
| year = 1544| publisher = apud Iohan Petreium }}. 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.{{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–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}}

Definition

{{See also|Signed-digit representation}}Let mathcal{D}_{3} := lbrace operatorname{T}, 0, 1 rbrace denote the set of symbols (also called glyphs or characters), where the symbol bar{1} is sometimes used in place of operatorname{T}. Define an integer-valued function f = f_{mathcal{D}_{3}} : mathcal{D}_{3} to mathbb{Z} by
f_{}(operatorname{T}) = -1, f_{}(0) = 0 quad and f_{}(1) = 1,The symbols 0 and 1 appear twice in the equalities f_{}(0) = 0 and f_{}(1) = 1, but these instances do not represent the same thing. The right hand side 0 and 1 mean the integers inZ, but the instances inside f's parentheses (which belong to mathcal{D}_{3}) should be thought of as being nothing more than symbols.
where the right hand sides are integers with their usual values. This function, f_{}, is what rigorously and formally establishes how integer values are assigned to the symbols/glyphs in 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 mathcal{D}_{3} together with the function 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 mathcal{D}_{3}^{+} be the Kleene plus of mathcal{D}_{3}, which is the set of all finite length concatenated strings d_n ldots d_0 of one or more symbols (called its digits) where n is a non-negative integer and all n + 1 digits d_n, ldots, d_0 are taken from mathcal{D}_{3} = lbrace operatorname{T}, 0, 1 rbrace. The start of d_n ldots d_0 is the symbol d_0 (at the right), its end is d_n (at the left), and its length is n + 1. The ternary evaluation is the function v = v_{3} ~:~ mathcal{D}_{3}^{+} to mathbb{Z} defined by assigning to every string d_n ldots d_0 in mathcal{D}_{3}^{+} the integer
vleft( d_n ldots d_0 right) ~=~ sum_{i=0}^{n} f_{} left( d_{i} right) 3^{i}.
The string d_n ldots d_0 represents (with respect to v) the integer vleft( d_n ldots d_0 right). The value vleft( d_n ldots d_0 right) may alternatively be denoted by {d_n ldots d_0}_{operatorname{bal}3}. The map v : mathcal{D}_{3}^{+} to mathbb{Z} is surjective but not injective since, for example, 0 = v(0) = v(00) = v(0 0 0) = cdots. However, every integer has exactly one representation under v that does not end (on the left) with the symbol 0, i.e. d_n = 0 .If d_n ldots d_0 in mathcal{D}_{3}^{+} and n > 0 then v satisfies:
vleft( d_n d_{n-1} ldots d_0 right) ~=~ f_{} left( d_{n} right) 3^{n} + vleft( d_{n-1} ldots d_0 right)
which shows that v satisfies a sort of recurrence relation. This recurrence relation has the initial conditionvleft( varepsilon right) = 0 where varepsilon is the empty string.This implies that for every string d_n ldots d_0 in mathcal{D}_{3}^{+},
vleft( 0 d_n ldots d_0 right) = vleft( d_n ldots d_0 right)
which in words says that leading 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 v can be computed, where (as before) all integer are written in decimal (base 10) and all elements of mathcal{D}_{3}^{+} are just symbols.
begin{alignat}{10}
vleft( operatorname{T} operatorname{T} right) &= && f_{}left( operatorname{T} right) 3^{1} + && f_{}left( operatorname{T} right) 3^{0} &&= &&(-1) &&3 &&,+, &&(-1) &&1 &&= -4 vleft( operatorname{T} 1 right) &= && f_{}left( operatorname{T} right) 3^{1} + && f_{}left( 1 right) 3^{0} &&= &&(-1) &&3 &&,+, &&(1) &&1 &&= -2 vleft( 1 operatorname{T} right) &= && f_{}left( 1 right) 3^{1} + && f_{}left( operatorname{T} right) 3^{0} &&= &&(1) &&3 &&,+, &&(-1) &&1 &&= 2 vleft( 1 1 right) &= && f_{}left( 1 right) 3^{1} + && f_{}left( 1 right) 3^{0} &&= &&(1) &&3 &&,+, &&(1) &&1 &&= 4 vleft( 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 vleft( 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}and using the above recurrence relation
vleft( 1 0 1 operatorname{T} right) = f_{}left( 1 right) 3^{3} + vleft( 0 1 operatorname{T} right) = (1) 27 + vleft( 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 3n. This is useful when converting between decimal and balanced ternary. In the following the strings denoting balanced ternary carry the suffix, bal3. For instance,
10bal3 = 1 × 31 + 0 × 30 = 3dec 10𝖳bal3 = 1 × 32 + 0 × 31 + (−1) × 30 = 8dec −9dec = −1 × 32 + 0 × 31 + 0 × 30 = 𝖳00bal3 8dec = 1 × 32 + 0 × 31 + (−1) × 30 = 10𝖳bal3
Similarly, the first place to the right of the radix point holds 3−1 = {{sfrac|1|3}}, the second place holds 3−2 = {{sfrac|1|9}}, and so on. For instance,
−{{sfrac|2|3}}dec = −1 + {{sfrac|1|3}} = −1 × 30 + 1 × 3−1 = 𝖳.1bal3.
{| class="wikitable" style="border: none; text-align:right"! Dec !! Bal3 !! Expansion
| 0
| +1
| +3−1
| +3
| +3+1
| +9−3−1
| +9−3
| +9−3+1
| +9−1
| +9
| +9+1
| +9+3−1
| +9+3
| +9+3+1
{| class="wikitable" style="border: none; text-align:right"! Dec !! Bal3 !! Expansion
| 0
| −1
| −3+1
| −3
| −3−1
| −9+3+1
| −9+3
| −9+3−1
| −9+1
| −9
| −9−1
| −9−3+1
| −9−3
| −9−3−1
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.WEB,weblink Balanced ternary, Bhattacharjee, Abhijit, 24 July 2006,weblink" title="web.archive.org/web/20090919053547weblink">weblink 2009-09-19,
{| class="wikitable"! Decimal! style="text-align: 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
010𝖳}}𝖳.{{overline10𝖳0}} 𝖳.{{overline𝖳}} or 𝖳.{{overline𝖳𝖳11}} 0.{{overline𝖳11𝖳}} 0.{{overline| 0
! Decimal! style="text-align: 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
0𝖳01}}1.{{overline𝖳010}} 1.{{overline1}} or 1.{{overline11𝖳𝖳}} 0.{{overline1𝖳𝖳1}} 0.{{overline| 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.12 = 0.1{{overline|0}}2 = 0.0{{overline|1}}2. Some balanced ternary fractions have multiple representations too. For example, {{sfrac|1|6}} = 0.1{{overline|𝖳}}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 after the radix point in order to gain a representations of integer or terminating fraction.Donald KnuthBOOK, Knuth, Donald, Donald Knuth, The art of Computer Programming, 2, 195–213, Addison-Wesley, 199711}} (round to 0, and truncate to 0) and 1.{{overlineradix, Rounding#Double rounding>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

{| class="wikitable" style="text-align: center;"!Fraction!!colspan="2"|Balanced ternary
1
11}}1.{{overline|𝖳}}
10.1
10.{{overline|1𝖳}}
10.{{overline|1𝖳𝖳1}}
11}}0.1{{overline|𝖳}}
10.{{overline|0110𝖳𝖳}}
10.{{overline|01}}
10.01
10.{{overline|010𝖳}}
{| class="wikitable" style="text-align: center;"!Fraction!!colspan="2"|Balanced ternary
10.{{overline|01𝖳11}}
10.0{{overline|1𝖳}}
10.{{overline|01𝖳}}
10.{{overline|01𝖳0𝖳1}}
10.0{{overline|1𝖳𝖳1}}
10.{{overline|01𝖳𝖳}}
10.{{overline|01𝖳𝖳𝖳10𝖳0𝖳111𝖳01}}
11}}0.01{{overline|𝖳}}
10.{{overline|00111𝖳10100𝖳𝖳𝖳1𝖳0𝖳}}
10.{{overline|0011}}
The conversion of a repeating balanced ternary number to a fraction is analogous to converting a repeating decimal. For example (because of 111111bal3 = ({{sfrac|36 − 1|3 − 1}})dec):
0.1overline{mathrm{110TT0} } =tfrac{mathrm{1110TT0-1} }{mathrm{111111times 1Ttimes 10}}=tfrac{mathrm{1110TTT} } {mathrm{111111times 1T0}} =tfrac{mathrm{111times 1000T} } {mathrm{111times 1001times 1T0}} =tfrac{mathrm{1111times 1T}}{mathrm{1001times 1T0}} =tfrac{1111}{10010}=tfrac{mathrm{1T1T}}{mathrm{1TTT0}} =tfrac{101}{mathrm{1T10} }

Irrational numbers

As in any other integer base, algebraic irrationals and transcendental numbers do not terminate or repeat. For example:
{| class="wikitable"
!Decimal !! Balanced ternary
| sqrt{mathrm{1T}}=mathrm{1.11T1TT00T00T01T0T00T00T01TTldots}
| sqrt{mathrm{10}}=mathrm{1T.T1TT10T0000TT1100T0TTT011T0ldots}
| sqrt{mathrm{1TT}}=mathrm{1T.1T0101010TTT1TT11010TTT01T1ldots}
| varphi=frac{1 + sqrt{mathrm{1TT}}}{mathrm{1T}}=mathrm{1T.T0TT01TT0T10TT11T0011T10011ldots}
| tau=mathrm{1T0.10TT0T1100T110TT0T1TT000001}ldots
| pi=mathrm{10.011T111T000T011T1101T111111}ldots
| e=mathrm{10.T0111TT0T0T111T0111T000T11T}ldots
The balanced ternary expansions of pi is given in OEIS as {{OEIS link|A331313}}, that of e in {{OEIS link|A331990}}.

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,
  • : 0213 + 113 = 1023, 1023 − 113 = 1T1bal3 = 7dec.
  • If a 2 is present in ternary, turn it into 1T. For example,
  • : 02123 = 0010bal3 + 1T00bal3 + 001Tbal3 = 10TTbal3 = 23dec
{| class="wikitable floatright" style=" text-align: center"! Balanced || Logic || Unsigned
| 2
| 1
| 0
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
b=leftlfloor frac{3^n}{2} rightrfloor
which is represented as all ones in either conventional or biased form.Douglas W. Jones, Ternary Number Systems, October 15, 2013.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

We may convert to balanced ternary with the following formula:
left(a_na_{n-1}cdots a_1a_0.c_1 c_2 c_3cdotsright)_b =
sum_{k=0}^n a_kb^k + sum_{k=1}^infty c_kb^{-k}.
where,
anan−1...a1a0.c1c2c3... is the original representation in the original numeral system. b is the original radix. b is 10 if converting from decimal. ak and ck are the digits k places to the left and right of the radix point respectively.
For instance,
−25.4dec = −(1T×1011 + 1TT×1010 + 11×101−1)
= −(1T×101 + 1TT + 11÷101)
= −10T1.{{overline|11TT}}
= T01T.{{overline|TT11}}


1010.12 = 1T10 + 1T1 + 1T−1
= 10T + 1T + 0.{{overline|1}}
= 101.{{overline|1}}

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.
{||
:{| class="wikitable" style="width: 8em; text-align: center;"
|+ Addition
|- align="right"
! + !! T !! 0 !! 1
|-
|-
! T
| T1 || T || 0
|-
! 0
| T || 0 || 1
|-
! 1
| 0 || 1 || 1T
|}|
:{| class="wikitable" style="width: 8em; text-align: center;"
|+ Subtraction
|- align="right"
! − !! T !! 0 !! 1
|-
! T
| 0 || T || T1
|-
! 0
| 1 || 0 || T
|-
! 1
| 1T || 1 || 0
|}|
:{| class="wikitable" style="width: 8em; text-align: center;"
|+ Multiplication
|- align="right"
! × !! T !! 0 !! 1
|-
|-
! T
| 1 || 0 || T
|-
! 0
| 0 || 0 || 0
|-
! 1
| T || 0 || 1
|}|
:{| class="wikitable" style="text-align: center;"
|+ Division
|- align="right"
! ÷ !! T !! 1
|-
|-
! T
| 1 || T
|-
! 0
| 0 || 0
|-
! 1
| T || 1
|}

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:
1TT1TT.1TT1 1TT1TT.1TT1 1TT1TT.1TT1 1TT1TT.1TT1
+ 11T1.T − 11T1.T − 11T1.T → + TT1T.1
______________ ______________ _______________
1T0T10.0TT1 1T1001.TTT1 1T1001.TTT1
+ 1T + T T1 + T T
______________ ________________ ________________
1T1110.0TT1 1110TT.TTT1 1110TT.TTT1
+ T + T 1 + T 1
______________ ________________ ________________
1T0110.0TT1 1100T.TTT1 1100T.TTT1

Multi-trit multiplication

Multi-trit multiplication is analogous to that of binary and decimal.
1TT1.TT
× T11T.1
_____________
1TT.1TT multiply 1
T11T.11 multiply T
1TT1T.T multiply 1
1TT1TT multiply 1
T11T11 multiply T
_____________
0T0000T.10T

Multi-trit division

Balanced ternary division is analogous to that of binary and decimal.However, 0.5dec = 0.1111...bal3 or 1.TTTT...bal3. 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,
1TT1.TT quotient
0.5 × divisor T01.0 _____________
divisor T11T.1 ) T0000T.10T dividend
T11T1 T000 < T010, set 1
_______
1T1T0
1TT1T 1T1T0 > 10T0, set T
_______
111T
1TT1T 111T > 10T0, set T
_______
T00.1
T11T.1 T001 < T010, set 1
________
1T1.00
1TT.1T 1T100 > 10T0, set T
________
1T.T1T
1T.T1T 1TT1T > 10T0, set T
________
0
Another example,
1TTT
0.5 × divisor 1T _______
Divisor 11 )1T01T 1T = 1T, but 1T.01 > 1T, set 1
11
_____
T10 T10 < T1, set T
TT
______
T11 T11 < T1, set T
TT
______
TT TT < T1, set T
TT
____
0
Another example,
101.TTTTTTTTT...
or 100.111111111...
0.5 × divisor 1T _________________
divisor 11 )111T 11 > 1T, set 1
11
_____
1 T1 < 1 < 1T, set 0
___
1T 1T = 1T, trits end, set 1.TTTTTTTTT... or 0.111111111...

Square roots and cube roots

The process of extracting the square root in balanced ternary is analogous to that in decimal or binary.
(10cdot x+y)^{mathrm{1T}}-100cdot x^{mathrm{1T}}=mathrm{1T0}cdot xcdot y+y^{mathrm{1T}}=
begin{cases}mathrm{T10}cdot x+1, & y=mathrm{T} mathrm{1T0}cdot x+1, & y=1end{cases}As in division, we should check the value of half the divisor first. For example,
1. 1 1 T 1 T T 0 0 ...
_________________________
√ 1T 1110, set 1
10T0 −10T0
________
111×10=1110 T1T0T T1T0T111T0, set 1
10T110 −10T110
__________
111T1×10=111T10 TT1TT0T TT1TT0T
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,"

- content above as imported from Wikipedia
- "balanced ternary" does not exist on GetWiki (yet)
- time: 8:38am EDT - Sat, May 18 2024
[ this remote article is provided by Wikipedia ]
LATEST EDITS [ see all ]
GETWIKI 23 MAY 2022
GETWIKI 09 JUL 2019
Eastern Philosophy
History of Philosophy
GETWIKI 09 MAY 2016
GETWIKI 18 OCT 2015
M.R.M. Parrott
Biographies
GETWIKI 20 AUG 2014
CONNECT