# 2017q3 Homework1 (Ternary)

contributed by < `BreezeDa` >

## 作業要求

- [x] 解釋 Balanced Ternary 原理
- [ ] Balanced Ternary 的設計要解決什麼類型的問題，需要詳述實際應用案例 (如 IOTA/Tangle)。提示：從算術表達的精準度和空間使用效率去探討;
- [ ] 針對特定的領域 (如加密貨幣)，列出在 GitHub 裡頭可找到的應用案例，不僅列出程式碼，還要解說
- [ ] 在研究的過程中，應該會對既有工具進行修改或者重新開發 (不限程式語言)，也該一併指出，程式碼應該維護在 GitHub 上

> [time=Wed, Oct 2, 2017 1:52 PM] 1st version
## Ternary
在講到 Balanced Ternary 之前我們先簡介一下 ternary，ternary 是以 3 為基數的進位方式，中文稱為`三進制`，我們知道 binary 使用 0,1 表示一個數字，而在 ternary 中我們則使用 0,1,2 來表示一個數字。下方是個 10 進位轉三進位的說明。

## Balanced Ternary

### 簡介

Balanced Ternary 與 ternary 不同，數值表示不使用 0, 1, 2 ， 而是 -1, 0, 1 ( 亦可標示為 T, 0, 1 或 -, 0, + )。而且由於 -1 的引入，這種進位不需要額外的符號就能直接表示負數。下方我們 基數符號使用 b3 表示 balanced ternary

### 數值表示

#### 整數

| decimal | balanced ternary |
|---------|------------------|
| -7 | T1T , -+\- |
| -5 | T11 , -++ |
| -2 | T1 , -+ |
| 2 | 1T , +\- |
| 5 | 1TT , +\-\- |
| 7 | 1T1 , +\-+ |

**解析**

$-7_{10} = T1T_{b3} = -1 \times 3 ^ 2 + 1 \times 3 ^ 1 + -1 \times 3 ^ 0$

$5_{10} = T1T_{b3} = 1 \times 3 ^ 2 + -1 \times 3 ^ 1 + -1 \times 3 ^ 0$

#### 小數

| decimal | balanced ternary |
|---------|------------------ |
| -0.5 | $\overline{0.T}$ or $\overline{T.1}$ |
| -0.4 | $\overline{0.TT11}$ |
| -0.1 | $\overline{0.0T01}$ |
| 0.1 | $\overline{0.010T}$ |
| 0.4 | $\overline{0.11TT}$ |
| 0.5 | $\overline{0.1}$ or $\overline{1.T}$ |

**解析**

* 一開始看到 $0.5_{10} = \overline{0.1}_{b3}$，還沒搞明白這兩個是怎麼個相等法，後來看到[benson326](https://hackmd.io/s/HJlqHCjqW)用等比級數的公式算一遍才頓悟。以下則是計算 $0.4_{10} =\overline{0.11TT}$ :

$\overline{0.11TT}_{b3} = 1 \times 3 ^ {-1} + 1 \times 3 ^ {-2} - 1 \times 3 ^ {-3} - 1 \times 3 ^ {-4} + 1 \times 3 ^ {-5} + 1 \times 3 ^ {-6} - 1 \times 3 ^ {-7} - 1 \times 3 ^ {-8} + ...\\
= 3 ^ {-1} + 3 ^ {-5} + 3 ^ {-9} +...\\
\ \ \ \ 3 ^ {-2} + 3 ^ {-6} + 3 ^ {-10} + ...\\
-(3 ^ {-3} + 3 ^ {-7} + 3 ^ {-11} + ...)\\
-(3 ^ {-4} + 3 ^ {-8} + 3 ^ {-12} + ...)$

$=\dfrac{3 ^ {-1}}{1-\dfrac{1}{3 ^ 4}} + \dfrac{3 ^ {-2}}{1-\dfrac{1}{3 ^ 4}} - \dfrac{3 ^ {-3}}{1-\dfrac{1}{3 ^ 4}} - \dfrac{3 ^ {-4}}{1-\dfrac{1}{3 ^ 4}} = 0.4_{10}$

* **由以上整數與小數的表示中可以看出正數與負數之間的轉換，其實只要將 1 轉成 T ，T 轉成 1 就可**

### 運算

latex 表格參考 [as23041248](https://hackmd.io/OwDmE4FMGMFZILQEMBGAmADAgLO7yBGFYBANm2jTBAGYUATSeoA=?both) 並增加減法，並分別給予一個計算範例

#### 加法

\begin{array}{c|ccc}
ADD & T & 0 & 1 \\
\hline
T & T1 & T & 0 \\
0 & T & 0 & 1 \\
1 & 0 & 1 & 1T
\end{array}

e.g. $T1TT + 1T1$

\begin{array}{ccccccccc}
& & & \tiny T \\
& & T & 1 & T & T\\
& + & & 1 & T & 1 \\
\hline
& & T & 1 & 1 & 0 \\
\end{array}

> $T+T = T1$ 我將 T 寫下一位上方
#### 減法

\begin{array}{c|ccc}
SUB & T & 0 & 1 \\
\hline
T & 0 & T & T1 \\
0 & 1 & 0 & T \\
1 & 1T & 1 & 0
\end{array}

>左欄減頂列

e.g. $T11T - 11TT$

\begin{array}{ccccccccc}
& & & & &\tiny T \\
& & & T & 1 & 1 & T\\
& - & & 1 & 1 & T & 1 \\
\hline
& & T & 1 & 0 & 1 & 1 \\
\end{array}
> $T -1 = T1$ 我將T寫在第二位的上方 => 第二位(由右往左數) $T + 1 -T = 1$
#### 乘法

\begin{array}{c|ccc}
MUL & T & 0 & 1 \\
\hline
T & 1 & 0 & T \\
0 & 0 & 0 & 0 \\
1 & T & 0 & 1
\end{array}

e.g. $T1T \times 1T$

\begin{array}{ccccccccc}
& & & T & 1 & T\\
& \times & & & 1 & T \\
\hline
& & & 1 & T & 1 \\
& + & & T & 1 & T\\
\hline
& & T & 1 & 1 & 1\\
\end{array}

### 效率

由 [Ripple Adder in Binary and Ternary Logic](https://www.youtube.com/watch?v=TfJxAb0owj8) 可以看出在 ripple adder 中同樣的運算，ternary logic 比標準 binary 來得快
:::danger
「所以應該」？這是理工人說的話嗎？

:notes:
:::

## 參考資料
[wikipedia: blanced ternary](https://en.wikipedia.org/wiki/Balanced_ternary)
[Ternary numeral system](https://en.wikipedia.org/wiki/Ternary_numeral_system)