Transcript balanced ternary notation

Balanced Ternary Notation
The Goldilocks of Numbering Systems
Brian Shelburne
Department of Mathematics and Computer Science
Wittenberg University
August 31, 2015
Abstract: There is base 10 and base 2 and base 16 (hexadecimal)
notation but why not base 3 (ternary) and in particular balanced
ternary notation? We’ll examine what balanced ternary notation
is and how to add, subtract, multiply, divide and take square
roots. There is some evidence that balanced ternary notation is
the most efficient of numbering systems, the so called
“Goldilocks” of numbering systems in that “base 2 is too small”,
“base 10 is too big”, and “base 3 is just right”.
“Perhaps the prettiest number system of all … is the balanced
ternary notation” –
Donald Knuth, The Art of Programming
A brief historical overview of numbering systems
The standard positional notations: decimal and binary
Why not ternary and balanced ternary?
Arithmetic operations in balanced ternary
Square roots? (with time)
Why ternary is the Goldilocks of positional notation – a proof?
Type A – Additive Systems (3 subtypes) “simple transcriptions of even more
concrete systems of counting”
A.1
A.2
A.3
Egyptian Hieroglyphic system
Roman Numerals
Greek Alphabetic
An Overview of
Numbering
Systems
Type B – Hybrid Systems (5 subtypes) “written transcriptions of more or less
organized verbal expressions of number” – additive and multiplicative
principle
B.1.
B.5.
Common Assyro-Babylonian
Common Chinese
Type C – Positional Systems (2 subtype)
C.1.
C.2.
Learned Babylonian; Learned Chinese
Mayan (base 20 – modified)
Indian -> Modern
Georges Ifrah “The Universal History of Numbers”
Egyptian Numerals
Greek Alphabetic (Learned)
Common Assyro-Babylonian
Common Chinese
Babylonian
Positional Notations: Decimal Base and Binary Notation
2413 = 2×103 + 4×102 + 1×101 + 3×100
1011101 = 1×26 + 0×25 +1×24 + 1×23 + 1×22 + 0×21 + 1×0
= 64 + 16 + 8 + 4 + 1 = 91
Also Octal (0135) and Hexadecimal (0x5D) Notation
Binary to Decimal Conversion: Expand by Powers of 2
Decimal to Binary Conversion: Subtract out Powers of 2
Example: Convert 413 to Binary
256
1
413
-256
157
128
1
64
0
157
-128
29
32
0
16
1
29
-16
11
8
1
4
0
11
- 8
3
2
1
1
1
3
-2
1
1
-1
0
Example: Convert 2413 to binary
2048
1024
256
128
64
32
Why Binary Notation: Pros and Cons?
16
8
4
2
1
Ternary (base 3) Notation
In Ternary natation we use three digits (0, 1, 2) and powers of 3
Example
12013 = 1×33 + 2×32 + 0×31 + 1×30 = 27 + 2×9 + 0 + 1 = 46
To convert Ternary to Decimal expand by powers of 3
To convert Decimal to Ternary subtract out (multiple) powers of 3
729
243
81
27
9
3
1
Example: Convert 413 to Ternary
243
486
1
413
-243
170
81
162
2
170
-162
8
27
54
0
9
18
0
8
- 6
2
Example: Convert 2413 to Ternary
3
6
2
2
- 2
0
1
2
2
Balanced (Signed) Ternary Notation
Instead the digits 0, 1, and 2 use (-1), 0, 1 so that negative digits are
used
Example:
1(-1)0(-1) = 1×33 + (-1)×32 + 0×31 + (-1)×30 = 27 – 9 – 1 = 17
To make things easier, use T, 0 ,1 for digits instead of (-1), 0, and 1
Example: 1T0T = 17
Aside: A capital Theta Θ which looks like a minus sign inside a circle
can be used for -1 so “T” stands for capital Theta.
Counting from -1 to 10
Decimal
Binary
Ternary
Balanced
Ternary
-1
-1
-1
T
00T
0
0
0
0
000
1
1
1
1
001
2
10
2
1T
01T
3
11
10
10
010
4
100
11
11
011
5
101
12
1TT
1TT
6
110
20
1T0
1T0
7
111
21
1T1
1T1
8
1000
22
10T
10T
9
1001
100
100
100
10
1010
101
101
101
Decimal - Balanced Ternary Conversions
Balanced Ternary to Decimal: Expand by Powers of 3
1T0T = 33 – 32 -30 = 27 – 9 – 1 = 17
Decimal to Balanced Ternary (2 steps)
Decimal to Ternary then
Ternary to Balanced Ternary.
From right to left convert 2 to 1T
Add the 1 to the next digit
17 = 1223 = 1(1T)(1T) = (1+1)(T+1)T = 1T0T
Convert 52 to balanced ternary
Addition and Subtraction
9 rules for addition:
1 + T cancel
0 + anything = anything
Only 2 rules have carries
To negate swap 1’s and T’s
To subtract, negate and add
T
T
--T1
T
0
--T
T
1
--0
0
T
--T
0
0
--0
0
1
--1
1
T
--0
1
0
--1
1
1
--1T
Advantages to Balanced Ternary Notation
Leading digit indicates sign of the number
Easy to “compare” numbers: 11T> 10T > 1TT
To negate any integer swap T’s and 1’s
if 17 = 1T0T then -17 = T101
Examples
1T0T = 17
+10TT = 23
-----1111 = 40
1T0T = 17
+T011 = -23
-----0T10 = -6
T101 = -17
+T011 = -23
-----TTTT = -40
-17
+23
--??
Multiplication
3 rules for multiplication:
10T = 8
× 10T = 8
------T01
000
+ 10T
--------1T101 = 81 –
1 × anything is anything - copy
0 × anything = 0
T × anything = swap T & 1: invert
invert
nothing
copy
17 = 1T0T
×23 = 10TT
-----391
27 + 9 + 1 = 64
Aside: Doubling a Number (multiplication by 1T)
Example: 47 × 2
1TT1T = 47
1T = 2
T11T1
1TT1T
10111 = 94
Left shift multiplicand
and add inverted
multiplicand
Division is done the normal way but makes effective use of
positive and negative divisors (make copies of both)
10T
T01
110T
| 101101
T01
1T1
T01
T0
T01
10T
0
280 / 8 = 35
If the current dividend is positive (leading
digit is 1) add the negative divisor, set
Quotient digit to 1 and bring down the
next digit
If the current dividend is negative (leading
digit is T) add the positive divisor, set
The quotient digit to T and break down the
next digit.
Otherwise bring down next digit and set
quotient digit to 0
More Division Examples
1T0 r 10
111 | 10000
TTT
TTT
TT0
111
10
81 / 13 = 6 r 3
00
10
111 r 11
100 | 11111
T00
T00
111
T00
111
T00
121/9 = 13 r 4
11
Note: The remainder in division might not be positive
1T0 r T
10 | 1T0T
T0
T0
T0
10
0T
00
0T
17 ÷ 3 = 6 r -1
The solution is to
add the divisor to
the remainder and
subtract 1 from the
dividend (add T)
1TT r 1T
10 | 1T0T
17 ÷ 3 = 5 r 2
1 6 . 5 2
Square Roots
| 2 73 . 00 00
Compute
1
1
273
------2 b
1 73
Starting from decimal point
2 6
1 56
partition digits into pairs
---------Call leading paired or unpaired
32 b
17
00
digits the “current dividend”
32 5
16
25
----------330 b
75 00
330 2
66 04
---------8 98
etc.
1 6 . 5 2
Square Roots
| 2 73 . 00 00
Starting with the current dividend
1
1
estimate the largest digit “current
------quotient” whose square is less
2 b
1 73
than or equal to the current
2 6
1 56
dividend
---------Subtract the “quotient squared”
32 b
17
00
from the current dividend and
32 5
16
25
bring down the next two digits.
----------330 b
75 00 Call the current quotient a
330 2
66 04
---------8 98
etc.
1 6 . 5 2
Square Roots
| 2 73 . 00 00
Double the “current quotient” a
1
1
and left shift it (multiply by 10).
------Find the largest digit b such that
2 b
1 73
10×a+b times b is less than the
2 6
1 56
current dividend. Subtract and
bring down the next two digits.
---------32 b
17
00
Repeat
32 5
16
25
----------330 b
75 00
330 2
66 04
---------8 98
etc.
1
T
1 0 T
| 1 T1 01
T
0 T1
1T b
1T T
T1 1
1T0
T10
1T0
T10
1 TT
0 10
b
T
1
T
T1 01
T1 0T
00 00
Square Roots
bring down next 2 digits
2 x current quotient + b
current dividend negative; try b = T
(2 x current quotient + b) × T
& subtract
1 0 T
| 1 T1 01
T
0 T1
1
T
1T b
1T T
T1 1
1T0
1T0
T10
1T0
b
T
1
T
1 TT
0 10
T1 01
1T 0T
00 00
Square Roots
Problem: |10| > |T1|; Therefore b = 0
Bring down next two digits
2 × current quotient + b
current dividend negative; try b = T
(2 x current quotient + b) × T
& subtract
Balanced Ternary in Retrospect
1. Ternary Numbers systems have been called the “Goldilocks”
numbering systems – binary is too small, decimal is too big but
ternary is just right
2. Balanced Ternary has less carry propagation; negating numbers is
easy; the mechanics of calculation are simplified
3. In the 1840’s Thomas Fowler an English self-taught mathematician
and inventor invented a calculating machine that used balanced
ternary to perform its calculations. Fowler observed that the
mechanics of calculation were simplified using balanced ternary.
4. There have been a few attempts to construct ternary computers.
In the 1950’s Nikolai Brousentsov at Moscow State University
designed a ternary computer called the Setun with a word length
of 18 “trits” (same range as a 28 bit computer) in stead of “bits”.
50 were build between 1958 and 1965. In 1973 G. Frieder at SUNY
Buffalo designed a base 3 machine called the “Ternac” along with
a software emulator for it.
5. In ternary a Flip-Flop is a Flip-Flap-Flop
Why is Ternary Notation the Goldilocks of Positional Notation?
If r is the radix (base) and w is the width of an integer (number of
digits) you want to minimize the product y = r∙w for some fixed
value C = rw (constraint).
Thus w = ln(C) / ln(r) so if you minimize y = r∙ (ln C /ln r)
1
ln  r   ln  C   r  ln  C 
ln  C 
dy
r


ln  r   1  0
2
2 
dr
 ln  r  
 ln  r  
ln  r   1
r e
Note that 3 is closer to e than 2.
If C = 1000
w10 = 3
w2 = log2(1000)≈9.97
w3 = log3(1000)≈6.26
y10 = 10×3=30
y2 = 2×9.97=19.94
y3 = 3×6.26=18.78
Any Questions?
Thank You
Brian Shelburne
Department of Mathematics
and Computer Science
Wittenberg University
10T/1011/1TT0
“Perhaps the prettiest number system of all … is the balanced ternary notation” –
Donald Knuth, The Art of Programming