# 2017q3 Homework1 (ternary)
contributed by <`xr2439`>

---
### Review by `williamchangTW`
- 作者文中對 ternary 有初步的了解，希望能對該技術做更深入的了解，能慢慢地完成作業需求
>小弟坐井觀天，如有冒犯請見諒[name="williamchangTW"]

---

## Balanced Ternary 簡介
此處的 Ternary 是指 Ternary Numeral System，即以三進制的方式記數。在 N 進制的數字系統中，我們常以數字 `0, 1, ..., N-1` 搭配基數 N 來表示數值。

若於三進制系統中，選用 `0, 1, 2` 搭配基數 3 來表示數值，則此系統稱為不平衡三進制 (Unbalanced Ternary)。若改採用 `-1, 0, 1` 搭配基數 3 來表示數值，則可以發現 -1, 0, 1 三個數字於數線上的原點對稱，故稱平衡三進制 (Balanced Ternary)。

平衡進制系統由於具有小於零的數字，故不須像其他進制系統，如日常所用的十進制，需要正負號 (sign) 來標記數值的正負。

## Notation
為了能夠更簡潔地表達，文章採用下列的標記法：

* 對於不平衡 N 進制系統的數字，採用 ==(數字)~N~== 表示
* 對於平衡 N 進制系統的數字，採用 ==(數字)~balN~== 表示
* 對於十進位系統，採用 ==Dec== 表示
* 對於平衡三進制系統，採用 ==Bal3== 表示
* 於平衡三進制系統中，採用 ==T== 表示 -1

## Balanced Ternary 表達式
本節將描述下列兩個主題：
* 如何轉成十進位數字
* 如何從 Unbalanced Ternary 轉換成 Balanced Ternary

### 轉換為十進位數字
對於任何 N 進制數字，

$$
(a_{n} a_{n-1} \cdots a_{1} a_{0}.
b_{1} b_{2} b_{3}\cdots )_{N} =
\sum_{k=0}^{n} a_kN^k +
\sum_{k=1}^{\infty} b_kN^{-k}
\quad (1)
$$

依照上述公式能將平衡三進制的數字轉為十進位。

下表列出 -4~4 (Dec) 所對應的平衡三進制數字

| Dec | Bal3 | Expansion | Dec | Bal3 | Expansion |
|-----:|-----:|----------:|-----:|-----:|----------:|
| 0 | 0 | 0 | | | |
| 1 | 1 | +1 | -1 | T | -1 |
| 2 | 1T | +3-1 | -2 | T1 | -3+1 |
| 3 | 10 | +3 | -3 | T0 | -3 |
| 4 | 11 | +3+1 | -4 | TT | -3-1 |

發現於 ==Bal3== 中，若要改變一個數字的正負號，僅需將表達式中 `1` 置換為 `T`，`T` 置換 `1`。

> 若欲改變一個數字的正負號，則 (1) 式中的 $a_k$ 及 $b_k$ 係數，應加上負號。而在平衡三進制系統中，於係數加上負號等同於做 `1` 與 `T` 置換的動作。[name=xr2439]

### 如何從 Unbalanced Ternary 轉換成 Balanced Ternary
有兩種轉換方式

第 1 種方式為從數字最左方的非零數字加一連串的 `1`，接著再減去同樣的數字，但不做借位。以 210~3~ 為例：

$$
\begin{split}
210_{3} &+ 111_{3} &&= 1021_{3} \\
1021_{3} &- 111_{3} &&= 1T10_{bal3}
\end{split}
$$

第 2 種方式為將 `2` 替換為 `1T` 來表示。以 220~3~ 為例：

$$
220_{3} = 0220_{3} = 1T00_{bal3} + 01T0_{bal3} = 10T0_{bal3}
$$

> 第 1 種方式的原理為，某一個數字若加上 A 這個數，再減去 A 則會變為原來的數字。此方法的 A 為一連串的 `1`，其用意為將(數值)~3~中原本的 2 消除。最後再透過不借位減去的方法轉換成 ==Bal3== 的數值
>
> 第 2 種方法的原理很直覺，由於 2~3~ = 1T~bal3~，將式子中的 2~3~ 拆項以 1T~bal3~ 表示。
> [name=xr2439]

## Balanced Ternary 的數值運算

### Logic Tables

| Sum | T | 0 | 1 |
|:---:|:-:|:-:|:-:|
| T | 1 | T | 0 |
| 0 | T | 0 | 1 |
| 1 | 0 | 1 | T |

| Carry | T | 0 | 1 |
|:-----:|:-:|:-:|:-:|
| T | T | 0 | 0 |
| 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 1 |

## 參考資料
[Wikipedia - 進位制](https://zh.wikipedia.org/wiki/%E8%BF%9B%E4%BD%8D%E5%88%B6)
[Wikipedia - Ternary numeral system](https://en.wikipedia.org/wiki/Ternary_numeral_system)
[Wikipedia - Balanced ternary](https://en.wikipedia.org/wiki/Balanced_ternary)
[Youtube - Non-Binary Computing](https://www.youtube.com/watch?v=TFTK074nG_M)
###### tags: `xr2439`, `sysprog-hw`