Balanced ternary is a
ternary numeral system (i.e. base 3 with three
digits) that uses a balanced
signed-digit representation
In mathematical notation for numbers, a signed-digit representation is a positional numeral system with a set of signed digits used to encode the integers.
Signed-digit representation can be used to accomplish fast addition of integers be ...
of the
integer
An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign ( −1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the languag ...
s in which the digits have the values
−1
In mathematics, −1 (also known as negative one or minus one) is the additive inverse of 1, that is, the number that when added to 1 gives the additive identity element, 0. It is the negative integer greater than negative two (−2) and less t ...
,
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 plus and minus signs, and , are mathematical symbols used to represent the notions of positive and negative, respectively. In addition, represents the operation of addition, which results in a sum, while represents subtraction, resul ...
; 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
Non-standard positional numeral systems here designates numeral systems that may loosely be described as positional systems, but that do not entirely comply with the following description of standard positional systems:
:In a standard positional ...
. It was used in some early computers
[ and also in some solutions of ]balance puzzle
A balance puzzle or weighing puzzle is a logic puzzle about balancing items—often coins—to determine which holds a different value, by using balance scales a limited number of times. These differ from puzzles that assign weights to items, ...
s.[
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
In mathematics, −1 (also known as negative one or minus one) is the additive inverse of 1, that is, the number that when added to 1 gives the additive identity element, 0. It is the negative integer greater than negative two (−2) and less t ...
, while 0 and 1 represent themselves. Other conventions include using '−' and '+' to represent −1 and 1 respectively, or using Greek letter
The Greek alphabet has been used to write the Greek language since the late 9th or early 8th century BCE. It is derived from the earlier Phoenician alphabet, and was the earliest known alphabetic script to have distinct letters for vowels as ...
theta
Theta (, ; uppercase: Θ or ; lowercase: θ or ; grc, ''thē̂ta'' ; Modern: ''thī́ta'' ) is the eighth letter of the Greek alphabet, derived from the Phoenician letter Teth . In the system of Greek numerals, it has a value of 9.
G ...
(Θ), which resembles a minus sign in a circle, to represent −1. In publications about the Setun
Setun (russian: Сетунь) was a computer developed in 1958 at Moscow State University. It was built under the leadership of Sergei Sobolev and Nikolay Brusentsov. It was the most modern ternary computer, using the balanced ternary numeral sys ...
computer, −1 is represented as overturned 1: "1".
Balanced ternary makes an early appearance in Michael Stifel
Michael Stifel or Styfel (1487 – April 19, 1567) was a German monk, Protestant reformer and mathematician. He was an Augustinian who became an early supporter of Martin Luther. He was later appointed professor of mathematics at Jena Univ ...
's book ''Arithmetica Integra'' (1544). It also occurs in the works of Johannes Kepler
Johannes Kepler (; ; 27 December 1571 – 15 November 1630) was a German astronomer, mathematician, astrologer, natural philosopher and writer on music. He is a key figure in the 17th-century Scientific Revolution, best known for his laws ...
and Léon Lalanne
Léon Louis Lalanne (; real surname: Chrétien-Lalanne; 3 July 1811 – 12 March 1892) was a French engineer and politician.
Life
Lalanne was born in Paris on 3 July 1811, as Léon Louis Chrétien, the son of François Julien Léon Chrétien, a ph ...
. Related signed-digit schemes in other bases have been discussed by John Colson
John Colson (1680 – 20 January 1760) was an English clergyman, mathematician, and the Lucasian Professor of Mathematics at Cambridge University.
Life
John Colson was educated at Lichfield School before becoming an undergraduate at Christ Chu ...
, John Leslie, Augustin-Louis Cauchy
Baron Augustin-Louis Cauchy (, ; ; 21 August 178923 May 1857) was a French mathematician, engineer, and physicist who made pioneering contributions to several branches of mathematics, including mathematical analysis and continuum mechanics. H ...
, and possibly even the ancient Indian Vedas
upright=1.2, The Vedas are ancient Sanskrit texts of Hinduism. Above: A page from the '' Atharvaveda''.
The Vedas (, , ) are a large body of religious texts originating in ancient India. Composed in Vedic Sanskrit, the texts constitute th ...
.[. Reprinted in ]
Definition
Let denote the set of symbols
A symbol is a mark, sign, or word that indicates, signifies, or is understood as representing an idea, object, or relationship. Symbols allow people to go beyond what is known or seen by creating linkages between otherwise very different co ...
(also called glyphs or characters) , where the symbol is sometimes used in place of
Define an integer
An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign ( −1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the languag ...
-valued function by
:
:[The symbol appears twice in the equality but these instances do not represent the same thing. The right hand side means the integer ]zero
0 (zero) is a number representing an empty quantity. In place-value notation such as the Hindu–Arabic numeral system, 0 also serves as a placeholder numerical digit, which works by Multiplication, multiplying digits to the left of 0 by th ...
but the instance of inside 's parentheses (which belongs to ) should be thought of as being nothing more than a symbol (without meaning). The reason for this is because although this article happened to choose (it is this choice introduced the ambiguity), this set could, for example, have instead been chosen to consist of the symbols This ambiguity can be removed by replacing "" with the sentence " is equal to the integer zero
0 (zero) is a number representing an empty quantity. In place-value notation such as the Hindu–Arabic numeral system, 0 also serves as a placeholder numerical digit, which works by Multiplication, multiplying digits to the left of 0 by th ...
" or with "" where the symbol denotes the usual integer value in base ten. The same is true of the symbol in the equality and
:
where the right hand sides are integers with their usual (decimal) values. This function, is what rigorously and formally establishes how integer values are assigned to the symbols/glyphs in 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 together with the function forms a balanced signed-digit representation
In mathematical notation for numbers, a signed-digit representation is a positional numeral system with a set of signed digits used to encode the integers.
Signed-digit representation can be used to accomplish fast addition of integers be ...
called the balanced ternary system.
It can be used to represent integers and real numbers.
Ternary integer evaluation
Let be the Kleene plus of , which is the set of all finite length concatenated
In formal language theory and computer programming, string concatenation is the operation of joining character strings end-to-end. For example, the concatenation of "snow" and "ball" is "snowball". In certain formalisations of concatenat ...
strings of one or more symbols (called its digits) where is a non-negative integer and all digits are taken from The start of is the symbol (at the right), its end is (at the left), and its length is . The ternary evaluation is the function defined by assigning to every string the integer
:
The string represents (with respect to ) the integer The value may alternatively be denoted by
The map is surjective
In mathematics, a surjective function (also known as surjection, or onto function) is a function that every element can be mapped from element so that . In other words, every element of the function's codomain is the image of one element o ...
but not injective since, for example, However, every integer has exactly one representation under that does not end (on the left) with the symbol i.e.
If and then satisfies:
:
which shows that satisfies a sort of recurrence relation
In mathematics, a recurrence relation is an equation according to which the nth term of a sequence of numbers is equal to some combination of the previous terms. Often, only k previous terms of the sequence appear in the equation, for a parameter ...
. This recurrence relation has the initial condition
where is the empty string.
This implies that for every string
:
which in words says that leading 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 can be computed, where (as before) all integer are written in decimal (base 10) and all elements of are just symbols.
:
and using the above recurrence relation
:
Conversion to decimal
In the balanced ternary system the value of a digit ''n'' places left of the radix point
A decimal separator is a symbol used to separate the integer part from the fractional part of a number written in decimal form (e.g., "." in 12.45). Different countries officially designate different symbols for use as the separator. The choi ...
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,
: 10bal3 = 1 × 31 + 0 × 30 = 310
: 10𝖳bal3 = 1 × 32 + 0 × 31 + (−1) × 30 = 810
: −910 = −1 × 32 + 0 × 31 + 0 × 30 = 𝖳00bal3
: 810 = 1 × 32 + 0 × 31 + (−1) × 30 = 10𝖳bal3
Similarly, the first place to the right of the radix point holds 3−1 = , the second place holds 3−2 = , and so on. For instance,
: −10 = −1 + = −1 × 30 + 1 × 3−1 = 𝖳.1bal3.
An integer is divisible by three if and only if the digit in the units place is zero.
We may check the parity
Parity may refer to:
* Parity (computing)
** Parity bit in computing, sets the parity of data for the purpose of error detection
** Parity flag in computing, indicates if the number of set bits is odd or even in the binary representation of the ...
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
A decimal separator is a symbol used to separate the integer part from the fractional part of a number written in decimal form (e.g., "." in 12.45). Different countries officially designate different symbols for use as the separator. The choi ...
.
:
In decimal or binary, integer values and terminating fractions have multiple representations. For example, = 0.1 = 0.1 = 0.0. And, = 0.12 = 0.12 = 0.02. Some balanced ternary fractions have multiple representations too. For example, = 0.1bal3 = 0.0bal3. 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 Knuth
Donald Ervin Knuth ( ; born January 10, 1938) is an American computer scientist, mathematician, and professor emeritus at Stanford University. He is the 1974 recipient of the ACM Turing Award, informally considered the Nobel Prize of computer sc ...
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 is not exceptional; it has two equally valid representations, and two equally valid truncations: 0. (round to 0, and truncate to 0) and 1. (round to 1, and truncate to 1). With an odd radix
In a positional numeral system, the radix or base is the number of unique digits, including the digit zero, used to represent numbers. For example, for the decimal/denary system (the most common system in use today) the radix (base number) is ...
, 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
The conversion of a repeating balanced ternary number to a fraction is analogous to converting a repeating decimal. For example (because of 111111bal3 = ()10):
:
Irrational numbers
As in any other integer base, algebraic irrationals and transcendental numbers do not terminate or repeat. For example:
:
The balanced ternary expansions of is given in OEIS
The On-Line Encyclopedia of Integer Sequences (OEIS) is an online database of integer sequences. It was created and maintained by Neil Sloane while researching at AT&T Labs. He transferred the intellectual property and hosting of the OEIS to the ...
as , that of in .
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 = 710.
*If a 2 is present in ternary, turn it into 1T. For example,
*: 02123 = 0010bal3 + 1T00bal3 + 001Tbal3 = 10TTbal3 = 2310
If the three values of ternary logic
In logic, a three-valued logic (also trinary logic, trivalent, ternary, or trilean, sometimes abbreviated 3VL) is any of several many-valued logic systems in which there are three truth values indicating ''true'', ''false'' and some indeterminat ...
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
Offset binary, also referred to as excess-K, excess-''N'', excess-e, excess code or biased representation, is a method for signed number representation where a signed number n is represented by the bit pattern corresponding to the unsigned numb ...
system.
If the ternary number has ''n'' trits, then the bias ''b'' is
:
which is represented as all ones in either conventional or biased form.
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 when computed using conventional unsigned ternary arithmetic. Similarly, if ''x'' and ''y'' are conventional unsigned ternary numbers, their sum is when computed using balanced ternary arithmetic.
Conversion to balanced ternary from any integer base
We may convert to balanced ternary with the following formula:
:
where,
: ''ana''''n''−1...''a''1''a''0.''c''1''c''2''c''3... 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.410 = −(1T×1011 + 1TT×1010 + 11×101−1)
= −(1T×101 + 1TT + 11÷101)
= −10T1.
= T01T.
1010.12 = 1T10 + 1T1 + 1T−1
= 10T + 1T + 0.
= 101.
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
In mathematics, a binary operation is commutative if changing the order of the operands does not change the result. It is a fundamental property of many binary operations, and many mathematical proofs depend on it. Most familiar as the name of ...
, 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.
:
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.510 = 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 mathematics, a square root of a number is a number such that ; in other words, a number whose '' square'' (the result of multiplying the number by itself, or ⋅ ) is . For example, 4 and −4 are square roots of 16, because .
...
in balanced ternary is analogous to that in decimal or binary.
:
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 1<1T<11, set 1
− 1
_____
1×10=10 1.0T 1.0T>0.10, set 1
1T0 −1.T0
________
11×10=110 1T0T 1T0T>110, set 1
10T0 −10T0
________
111×10=1110 T1T0T T1T0T111T0, set 1
10T110 −10T110
__________
111T1×10=111T10 TT1TT0T TT1TT0T(10\cdot x+y)^-1000\cdot x^=y^+1000\cdot x^\cdot y+ 100\cdot x\cdot y^=
\begin
\mathrm+\mathrm\cdot x^+100\cdot x, & y=\mathrm\\
0, & y=0\\
1+1000\cdot x^+100\cdot x, & y=1
\end
Like division, we should check the value of half the divisor first too.
For example:
1. 1 T 1 0 ...
_____________________
³√ 1T
− 1 1<1T<10T,set 1
_______
1.000
1×100=100 −0.100 borrow 100×, do division
_______
1TT 1.T00 1T00>1TT, set 1
1×1×1000+1=1001 −1.001
__________
T0T000
11×100 − 1100 borrow 100×, do division
_________
10T000 TT1T00 TT1T001T1T01TT, set 1
11T×11T×1000+1=11111001 − 11111001
______________
1T10T000
11T1×100 − 11T100 borrow 100×, do division
__________
10T0T01TT 1T0T0T00 T01010T11<1T0T0T00<10T0T01TT, set 0
11T1×11T1×1000+1=1TT1T11001 − TT1T00 return 100×
_____________
1T10T000000
...
Hence = 1.25992110 = 1.1T1 000 111 001 T01 00T 1T1 T10 111bal3.
Applications
In computer design
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
Setun (russian: Сетунь) was a computer developed in 1958 at Moscow State University. It was built under the leadership of Sergei Sobolev and Nikolay Brusentsov. It was the most modern ternary computer, using the balanced ternary numeral sys ...
, built by Nikolay Brusentsov
Nikolay Petrovich Brusentsov (russian: Никола́й Петро́вич Брусенцо́в; 7 February 1925 in Kamenskoe, Ukrainian SSR – 4 December 2014) was a computer scientist, most famous for having built a ( balanced) ternary compute ...
and Sergei Sobolev
Prof Sergei Lvovich Sobolev (russian: Серге́й Льво́вич Со́болев) HFRSE (6 October 1908 – 3 January 1989) was a Soviet mathematician working in mathematical analysis and partial differential equations.
Sobolev introduced ...
. 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
In mathematics, a multiplication table (sometimes, less formally, a times table) is a mathematical table used to define a multiplication operation for an algebraic system.
The decimal multiplication table was traditionally taught as an essenti ...
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.
"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 as many digit positions for its representation."
"Perhaps the symmetric properties and simple arithmetic of this number system will prove to be quite important some day."
Other applications
The theorem that every integer has a unique representation in balanced ternary was used by Leonhard Euler
Leonhard Euler ( , ; 15 April 170718 September 1783) was a Swiss mathematician, physicist, astronomer, geographer, logician and engineer who founded the studies of graph theory and topology and made pioneering and influential discoveries ...
to justify the identity of formal power series
In mathematics, a formal series is an infinite sum that is considered independently from any notion of convergence, and can be manipulated with the usual algebraic operations on series (addition, subtraction, multiplication, division, partial s ...
:
Balanced ternary has other applications besides computing. For example, a classical two-pan balance
Balance or balancing may refer to:
Common meanings
* Balance (ability) in biomechanics
* Balance (accounting)
* Balance or weighing scale
* Balance as in equality or equilibrium
Arts and entertainment Film
* ''Balance'' (1983 film), a Bulgaria ...
, 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 (6010 = 1T1T0bal3) 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¤ (710 = 1T1bal3), the buyer pays 1¤ + 9¤ and receives 3¤ in change.
They may also provide a more natural representation for the qutrit
A qutrit (or quantum trit) is a unit of quantum information that is realized by a 3-level quantum system, that may be in a superposition of three mutually orthogonal quantum states.
The qutrit is analogous to the classical radix-3 trit, just as ...
and systems that use it.
See also
* Methods of computing square roots
* Numeral system
A numeral system (or system of numeration) is a writing system for expressing numbers; that is, a mathematical notation for representing numbers of a given set, using digits or other symbols in a consistent manner.
The same sequence of symbo ...
* Qutrit
A qutrit (or quantum trit) is a unit of quantum information that is realized by a 3-level quantum system, that may be in a superposition of three mutually orthogonal quantum states.
The qutrit is analogous to the classical radix-3 trit, just as ...
* Salamis Tablet
* Ternary computer
A ternary computer, also called trinary computer, is one that uses ternary logic (i.e., base 3) instead of the more common binary system (i.e., base 2) in its calculations. This means it uses trits (instead of bits, as most computers do).
Types ...
** Setun
Setun (russian: Сетунь) was a computer developed in 1958 at Moscow State University. It was built under the leadership of Sergei Sobolev and Nikolay Brusentsov. It was the most modern ternary computer, using the balanced ternary numeral sys ...
, a ternary computer
* Ternary logic
In logic, a three-valued logic (also trinary logic, trivalent, ternary, or trilean, sometimes abbreviated 3VL) is any of several many-valued logic systems in which there are three truth values indicating ''true'', ''false'' and some indeterminat ...
References
External links
Development of ternary computers at Moscow State University
"Third base"
ternary and balanced ternary number systems
The Balanced Ternary Number System
(includes decimal integer to balanced ternary converter)
*
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)
The ternary calculating machine of Thomas Fowler
by Mark Glusker
Computer arithmetic
Non-standard positional numeral systems
Ternary computers
Numeral systems
de:Ternärsystem#Balanciert