###### tags: `homework` `sysprog2017`
**2017q3 Homework1 (ternary)**
===
contributed by <`Jetudie`>

---
題目： [C01: Ternary](https://hackmd.io/s/Sym0UAk9Z)

## Balanced Ternary 簡介
### What's Ternary ?
也可稱為 three-valued logic。Ternary 用三個真值 (truth value) 表示 $true$ 和 $false$ ，還有第三個「不確定值」(indeterminate value)。

Ternary 中又有各種不同的數值表示法 (Representation of values)，例如：

| truth value | unsigned | balanced |
| :---------: | :------: | :------: |
| false | 0 | - |
| unknown | 1 | 0 |
| true | 2 | + |

--from [Fast Ternary Addition](http://homepage.divms.uiowa.edu/~jones/ternary/arith.shtml#reps "ternary number representations")

---
### Efficiency
#### ternary 與 binary 相比
[Fast Ternary Addition](http://homepage.divms.uiowa.edu/~jones/ternary/arith.shtml#reps) 寫道 "*A single digit in number base $b$ carries $log_2b$ bits of information. Thus, each ternary digit or trit carries about 1.58 bits, as compared to 3.32 bits per decimal digit.*"

試著算算看 ternary (base 3)
$2^b=3^t$
$b \times log2=t \times log3$
$b/t=log_23 \approx 1.58$

decimal (base 10) 作法也相仿
$b/d=log_210 \approx 3.32$

但這又代表著什麼？ base 越大就表示起來就越有效率？

#### Base $e$ 最「經濟」
+ 以下，是根據 [What is the most efficient numerical base system?](https://math.stackexchange.com/questions/446664/what-is-the-most-efficient-numerical-base-system) 解釋，為何在 [Non-integer representation](https://en.wikipedia.org/wiki/Non-integer_representation) 中提到，以 $e$ 作為基數 ([base/radix](https://en.wikipedia.org/wiki/Radix)) 是比 1 大的基數中最「經濟」的選擇：

1. 假設有 V 個獨立狀態 (independent state) 的資訊， 可以 base-N 表示成 $V/N$ 個位元 (digit)
2. 可表示的資訊量為 $I=N^{V/N}$
3. 最「經濟」的 base 就是能使 $I$ 最大的 $N$ 值
4. 對等號兩邊取自然對數 $ln(I)=(V/N)ln(N)$
5. 等號兩邊對 $N$ 微分 $(ln(I))'=(V/N^2)(1-ln(N))$
6. 做第二次對 $N$ 微分 $(ln(I))''=(V/N^3)(2ln(N)-3)$
7. 當 $N=e$ , $ln(I)$ 為極值， $(ln(I))'=0$
8. 當 $N=e$ , $(ln(I))''=-1/N^3$ 為負
9. 因此， $N=e$ 時， $I$ 有最大值(最為「經濟」)

+ [radix economy](https://en.wikipedia.org/wiki/Radix_economy) 中定義在給定的 base b 對於數值 N 的 radix economy
$E(b,N)=b\lfloor{\log_b (N)+1}\rfloor$ 即
$E(b,N)=b \times (表示N所需的位元數)$
$E(b,N)$ 愈小，代表以 base b 表示 N 的效率越高

---
### Balanced Ternary
Balanced ternary 用 "trit" ， 也就是 `-1` , `0` , `1` 表示數值，也常以`-` , `0` , `+` 或 `T` , `0` , `1` 代替，其特點在於==不須另外加負號就能表示所有整數==。

#### 與十進位之間的轉換

$\mathsf { 10T_{bal3} = 1 \times 3^2 + 0 \times 3^1 + (-1) \times 3^0 = 3_{dec} \\
-9_{dec} = -1 \times 3 ^2 + 0 \times 3^1 + 0 \times 3^0 = T00_{bal3} \\
-2/3_{dec} = -1 + 1/3 = -1 \times 3^0 + 1 \times 3^{-1} = T.1_{bal3} }$

再來看看 3-trit ternary numbers

$$
\begin{array}{cl|cl}
decimal & bal3 & decimal & bal3\\
\hline
-13 & --- & 13 & +++ \\
-12 & --0 & 12 & ++0 \\
-11 & --+ & 11 & ++- \\
-10 & -0- & 10 & +0+ \\
-9 & -00 & 9 & +00 \\
-8 & -0+ & 8 & +0- \\
-7 & -+- & 7 & +-+ \\
-6 & -+0 & 6 & +-0 \\
-5 & -++ & 5 & +-- \\
-4 & 0-- & 4 & 0++ \\
-3 & 0-0 & 3 & 0+0 \\
-2 & 0-+ & 2 & 0+- \\
-1 & 00- & 1 & 00+ \\
& & 0 & 000 \\
\end{array}
$$

觀察一下會發現：
__如果要知道一個數的負數的相反數(opposite number)只要把 bal3 表示的 `+` 跟 `-` 反過來即可__

--from [Hackaday 10th Anniversary: Non-Binary Computing](https://www.youtube.com/watch?v=TFTK074nG_M "youtube")

---

### Half Adder and Full Adder

#### Sum
回顧一下，在 Boolean Logic 中，我們以 xor 來表示兩個 1-bit binary 相加和 (sum)；但在 Balanced ternary 的 xor 則不會算出 sum。
但有另外定義一個 sum operator 表示如下：


$\begin{array}{cc|ccc}
& & & b & \\
& c & T & 0 & 1 \\
\hline
& T & 1 & T & 0 \\
a & 0 & T & 0 & 1 \\
& 1 & 0 & 1 & T \\
\end{array}$

說明：
0 加任何數，就等於此數本身
1 跟 T 相加為 0
T 加 T 會是 T1 ( carry = T, sum = 1 )
1 加 1 會是 1T ( carry = 1, sum = T )

#### Consensus
若兩者皆為 T 則為 T ，兩者皆為 1 則為 1 ，其餘皆為 0 。類似於 binary 中的 and 。


$\begin{array}{cc|ccc}
& & & b & \\
& c & T & 0 & 1 \\
\hline
& T & T & 0 & 0 \\
a & 0 & 0 & 0 & 0 \\
& 1 & 0 & 0 & 1 \\
\end{array}$

#### Accept Anything
和 consensus 相對應的 operator 為 accept anything (或 gullibility)。 consensus 除了接收到兩個相同的 $true$ 或 $false$ 才能確定為其一，其餘皆輸出 $unknown$ ； accept anything 則只會在都是 $unknown$ 或是一個 $true$ 和一個 $false$ 時，才輸出 $unknown$ 。

$\begin{array}{cc|ccc}
& & & b & \\
& c & T & 0 & 1 \\
\hline
& T & T & T & 0 \\
a & 0 & T & 0 & 1 \\
& 1 & 0 & 1 & 1 \\
\end{array}$

#### Balanced Half Adder

半加器的真值表 (truth table)

$\begin{array}{cc|cc}
input && output\\
a_i & c_i & c_{i+1} & s_i \\
\hline
T & T & T & 1 \\
T & 0 & 0 & T \\
T & 1 & 0 & 0 \\
0 & T & 0 & T \\
0 & 0 & 0 & 0 \\
0 & 1 & 0 & 1 \\
1 & T & 0 & 0 \\
1 & 0 & 0 & 1 \\
1 & 1 & 1 & T \\
\end{array}$

#### Balanced Full Adder
若依照 binary 的方法，以兩個 half adder 建構一個 full adder

會發現 c~a~ 跟 c~b~ 不會出現同時為 T 或同時為 1 的情況

$\begin{array}{cc|ccc}
& & & c_b & \\
& c & T & 0 & 1 \\
\hline
& T & & T & 0 \\
c_a & 0 & T & 0 & 1 \\
& 1 & 0 & 1 & \\
\end{array}$

必須進行優化 (optimization)，但優化後會變成複雜的形式。若我們只考慮複雜度，並且使用 ripple-carry logic ， balanced ternary 並非做一個三進位 ALU 的首選。

--from [Standard Ternary Logic](http://homepage.divms.uiowa.edu/~jones/ternary/logic.shtml "Standard Ternary Logic")

---

## Application on Solving Problems
Balanced Ternary 的設計要解決什麼類型的問題，需要詳述實際應用案例 (如 IOTA/Tangle)。提示：從算術表達的精準度和空間使用效率去探討